LeetCode 93. 复原 IP 地址
题目描述
:::fold 历史考题
考察公司：作业帮
考察时间：2025.5.27
:::
题意分析
给定一个只包含数字的字符串
s，只能在字符之间插入三个点，将它分成恰好四段，返回所有合法的 IPv4 地址。字符顺序不能改变，也不能删除任何字符，因此四段必须完整覆盖原字符串。每段都必须非空，表示的整数在
0到255之间，且不能含前导零；数值为零时只能由单个字符0构成。每段最多三位，所以只有长度在4到12之间的字符串才可能有答案。结果顺序不限，无法组成合法地址时返回空列表。
解法：回溯枚举每段
核心思路
[!blue]
地址的区别只在于三个分隔点放在哪里。可以从左向右依次确定每一段：在当前起点尝试长度为一、二、三的子串，合法就继续划分后面的部分。这些选择构成一棵深度最多为四的搜索树，用回溯逐个枚举。
递归状态中的
start是第一个尚未使用的字符下标，parts保存已经确定的合法段。它们始终恰好覆盖s的前start个字符。每次加入一段后，从这段之后的位置递归；返回时删除刚加入的段，使下一种长度的尝试仍从同一个已选前缀出发。搜索前先判断剩余长度能否分完。设还剩
segments = 4 - parts.size()段，剩余字符数为chars = s.length() - start。每段至少一位、至多三位，因此必须满足segments <= chars <= 3 * segments；不满足时，无论如何切分都不可能成功，可以直接返回。构造当前段时，逐位计算
value = value * 10 + 当前数字。若首位是0，只允许长度为一，再扩展就一定带前导零；若数值超过255，继续添加数字也不会重新合法。这两种情况都可以停止扩展当前段，而不只是跳过当前长度。凑满四段后，只有
start恰好等于字符串长度才收集答案。任何合法地址的每一段都在尝试的长度范围内，并且不会被上述合法性判断或长度剪枝排除，所以不会漏解；每组分段边界只会沿一条搜索路径产生，因此也不需要额外去重。
解题步骤
- 初始化结果列表和空的
parts，从start = 0开始回溯。- 若已有四段，检查是否恰好用完字符串；是则用点连接四段加入结果，然后结束当前分支。
- 根据剩余段数检查剩余字符数量，不在允许范围内就返回。
- 从
start起依次尝试一至三位，逐位累加数值；出现前导零或超过255时停止扩展。- 将合法子串加入
parts，从end + 1递归；递归返回后移除这一段，继续尝试下一种长度。- 所有分支处理完成后返回结果列表。
代码实现
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> answer = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), answer);
return answer;
}
private void backtrack(String s, int start, List<String> parts, List<String> answer) {
// 四段都已确定后，还必须恰好消费全部输入字符。
if (parts.size() == 4) {
if (start == s.length()) {
answer.add(String.join(".", parts));
}
return;
}
int chars = s.length() - start;
int segments = 4 - parts.size();
// 剩余每段至少一位、最多三位，超出范围就无需继续搜索。
if (chars < segments || chars > segments * 3) {
return;
}
int value = 0;
for (int end = start; end < s.length() && end < start + 3; end++) {
// 零可以单独成段，但不能作为多位段的前导零。
if (end > start && s.charAt(start) == '0') {
break;
}
value = value * 10 + s.charAt(end) - '0';
if (value > 255) {
break;
}
parts.add(s.substring(start, end + 1));
backtrack(s, end + 1, parts, answer);
// 撤销本段，让下一种切分复用原前缀。
parts.remove(parts.size() - 1);
}
}
}
func restoreIpAddresses(s string) []string {
answer := make([]string, 0)
parts := make([]string, 0, 4)
var backtrack func(int)
backtrack = func(start int) {
// 四段都已确定后，还必须恰好消费全部输入字符。
if len(parts) == 4 {
if start == len(s) {
answer = append(answer, parts[0]+"."+parts[1]+"."+parts[2]+"."+parts[3])
}
return
}
chars, segments := len(s)-start, 4-len(parts)
// 剩余每段至少一位、最多三位，超出范围就无需继续搜索。
if chars < segments || chars > segments*3 {
return
}
value := 0
for end := start; end < len(s) && end < start+3; end++ {
// 零可以单独成段，但不能作为多位段的前导零。
if end > start && s[start] == '0' {
break
}
value = value*10 + int(s[end]-'0')
if value > 255 {
break
}
parts = append(parts, s[start:end+1])
backtrack(end + 1)
// 撤销本段，让下一种切分复用原前缀。
parts = parts[:len(parts)-1]
}
}
backtrack(0)
return answer
}
复杂度分析
- 时间复杂度：$O(1)$。IPv4 固定为四段，最多进行四次分段，每次最多尝试三种长度，叶子数不超过 $3^4$；每个结果含至多十二个数字和三个点，拼接开销也有固定上界。长度不在允许范围内的输入在首次递归时直接结束，不会扫描整个字符串。
- 空间复杂度：$O(1)$，不计返回结果。递归最多深入四次，路径中最多保存四段，每段长度最多三。
关键点总结
[!green]
- 状态由“下一个字符位置”和“已选段”组成，已选段始终完整覆盖已消费的前缀。
- 局部合法性检查约束当前段，剩余长度剪枝判断整个后缀是否还有可能分完。
- 完成条件同时要求四段和字符全部用完；加入一段、递归、撤销这一段必须配套。
易错点总结
[!yellow]
- 只检查整数大小会丢失前导零信息，必须同时检查子串首位和长度。
- 一看到首位为
0就退出，会漏掉合法的单字符零段；应先允许长度为一的分支，再禁止继续扩展。- 凑满四段就收集答案，会误把仍有剩余字符的前缀当成完整地址。
- 递归返回后没有移除刚加入的段，会让不同切分分支共享错误的路径内容。
end是当前段最后一个字符的下标，截取子串和下一次递归的起点都应使用end + 1。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 468. 验证IP地址 | 中等 | 原题验证一个IP地址，本题枚举分段后也必须检查每段范围与前导零。 |
| 131. 分割回文串 | 中等 | 同样按子串分段回溯，原题每段需回文，本题必须四段且每段满足IPv4规则。 |