LeetCode LCR 087. 复原 IP 地址
目录
题目描述
题意分析
给一个只含数字的字符串
s，在其中插入三个点，把它切成四段，使每一段都是合法的 IPv4 地址段，返回所有可能的结果。不能重排、不能增删任何字符，只能决定三个点插在哪里。
「合法段」的定义要抠准，它由三条独立的规则组成：段的数值在
[0, 255]之间；段的长度在 1 到 3 之间（这条其实被前一条与下一条蕴含，但写代码时当作循环上界很方便）；除了单独的"0"之外不允许有前导零，所以"01"、"00"、"012"都非法，而"0"合法。第三条是本题最容易漏的规则，也是出题人真正想考的细节。
题目要输出所有方案，说明必须枚举。切法的总数很有限：三个点各自有不超过 3 种相对位置，粗算不超过 $3^3 = 27$ 种组合，因此本题的难点从来不是效率，而是把三条合法性规则不遗漏地编码进搜索。
约束
1 ≤ s.length ≤ 20且只含数字，这给出一个立刻可用的信号：四段最多覆盖 12 个字符，所以长度超过 12 的输入必然无解；长度小于 4 的输入同样无解。边界还包括："0000"应输出"0.0.0.0"（四个单零全合法）；"25525511135"这类恰好卡在 255 附近的输入要能正确区分"255"与"256"；无解时返回空列表而不是含空串的列表。
解法：回溯搜索
核心思路
骨架仍是「枚举分割点」：
dfs(i)表示s[0..i-1]已经被切成若干合法段并存在t中，当前要决定从下标i开始的这一段延伸到哪里。每层横向枚举段尾j，合法就递归dfs(j + 1)。
与「分割回文串」的差别在于本题有两个必须同时满足的终止条件：字符要用完（
i == n），段数要恰好是 4（t.size() == 4）。只满足其一都不算答案。字符用完但只切了 3 段，说明段切得太长；切满 4 段但还剩字符，说明段切得太短。这两种失败必须分别识别并及时返回，否则会产出残缺答案。
剪枝的关键观察是：段的合法性判断可以在逐字符延伸的过程中增量完成，而且一旦失效就再也不会恢复，因此可以用
break而不是continue。具体地，在内层循环里维护x表示s[i..j]的数值，每延长一位就x = x * 10 + (s[j] - '0')。
于是两条
break条件成立：x > 255时继续延长只会让数值更大，本段及其后所有更长的切法全部无效；s[i] == '0' && i != j时说明本段以 0 开头且长度大于 1，前导零已经出现，再延长依然带前导零。两者都是单调失效的性质，所以用break整体截断，而不是逐个continue跳过。
循环上界
j < min(i + 3, n)把段长限制在 3 以内，同时防止越界。要维持的不变量是：t中每一段都合法，且t拼接起来恰好等于s[0..i-1]。
解题步骤
- 成功条件放最前：
if (i >= n && t.size() == 4)时用.把四段连接成 IP 存入答案并返回。两个条件必须同时成立，缺一都不是合法答案。
- 失败条件紧随其后：
if (i >= n || t.size() >= 4) return;。走到这里说明上一个判断没通过，那么要么字符用完了但段数不够，要么段数已满但字符没用完，两种情况都无解，直接剪枝。把这一步写在循环之前，可以避免在段数已满时还去做无谓的横向枚举。
- 初始化本段数值：
int x = 0;，放在循环外，随j的推进累积。用数值累加而不是每次Integer.parseInt(substring)，既省去反复建子串的开销，也让x > 255的剪枝可以在延伸途中立即触发。
- 枚举段尾并增量求值：
for (int j = i; j < Math.min(i + 3, n); ++j)中x = x * 10 + s.charAt(j) - '0'。上界取i + 3与n的较小值，前者限制段长不超过 3，后者防越界。
- 两条
break剪枝：if (x > 255 || (s.charAt(i) == '0' && i != j)) break;。前导零条件写成s.charAt(i) == '0' && i != j，含义是「本段首字符是 0 且本段长度大于 1」；i == j时是单独的"0"，必须放行。
- 选择、递归、撤销：
t.add(s.substring(i, j + 1))，递归dfs(j + 1)，返回后t.remove(t.size() - 1)。递归传j + 1是下一段的起点。
以
s = "10203"走一遍，n = 5。四段总长必须是 5，所以各段长度只能是(2,1,1,1)、(1,2,1,1)、(1,1,2,1)、(1,1,1,2)四种分配之一。
dfs(0)，t = []，x从 0 开始。j = 0：x = 1，不超 255，首字符'1'不触发前导零，切出"1"，进入dfs(1)。
dfs(1)：s[1] = '0'。j = 1时x = 0，i == j所以前导零规则放行，切出"0"，进入dfs(2)。dfs(2)中j = 2切出"2"进入dfs(3)；dfs(3)里s[3] = '0'，j = 3切出"0"进入dfs(4)——此时i = 4 < n但t.size() == 4，命中失败条件返回；回到dfs(3)的j = 4，s[3] == '0' && i != j触发break，"03"被正确否决。
回到
dfs(2)的j = 3：x = 2 * 10 + 0 = 20，切出"20"，进入dfs(4)；dfs(4)中j = 4切出"3"，进入dfs(5)，此时i = 5 >= n且t.size() == 4，记下第一个答案"1.0.20.3"。继续dfs(2)的j = 4：x = 203，不超 255，切出"203"进入dfs(5)，但t.size()只有 3，落入失败条件返回。
回到
dfs(1)的j = 2：s[1] == '0'且i != j，break，"02"被否决——这正是前导零规则挡掉的分配(1,2,1,1)。
回到
dfs(0)的j = 1：x = 10，切出"10"进入dfs(2)；沿"2"、"0"、"3"一路下去在dfs(5)处凑满四段，记下第二个答案"10.2.0.3"。该分支的其它切法（如"10","20","3"只有三段）都在失败条件处被拦下。dfs(0)的j = 2：x = 102，切出"102"，其后最多再凑出"0"、"3"两段，总数不足 4，全部失败。
最终答案是
["1.0.20.3", "10.2.0.3"]。若漏掉前导零判断，会额外产出"1.02.0.3"和"1.0.2.03"两个非法结果。
代码实现
class Solution {
private int n;
private String s;
private List<String> answer = new ArrayList<>();
private List<String> t = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
n = s.length();
this.s = s;
dfs(0);
return answer;
}
// i：当前待切分段的起点，s[0..i-1] 已切成 t 中的若干合法段。
private void dfs(int i) {
// 字符用完且恰好四段，才是答案。
if (i >= n && t.size() == 4) {
answer.add(String.join(".", t));
return;
}
// 字符用完但段数不足，或段数已满但字符没用完，都无解。
if (i >= n || t.size() >= 4) {
return;
}
int x = 0;
// 段长最多 3，同时不越界。
for (int j = i; j < Math.min(i + 3, n); ++j) {
x = x * 10 + s.charAt(j) - '0';
// 超过 255 或出现前导零后，继续延长只会更糟，直接 break。
if (x > 255 || (s.charAt(i) == '0' && i != j)) {
break;
}
t.add(s.substring(i, j + 1));
dfs(j + 1);
t.remove(t.size() - 1);
}
}
}
func restoreIpAddresses(s string) (answer []string) {
n := len(s)
t := []string{}
// i：当前待切分段的起点，s[0..i-1] 已切成 t 中的若干合法段。
var dfs func(int)
dfs = func(i int) {
// 字符用完且恰好四段，才是答案。
if i >= n && len(t) == 4 {
answer = append(answer, strings.Join(t, "."))
return
}
// 字符用完但段数不足，或段数已满但字符没用完，都无解。
if i >= n || len(t) == 4 {
return
}
x := 0
// 段长最多 3，同时不越界。
for j := i; j < i+3 && j < n; j++ {
x = x*10 + int(s[j]-'0')
// 超过 255 或出现前导零后，继续延长只会更糟，直接 break。
if x > 255 || (j > i && s[i] == '0') {
break
}
t = append(t, s[i:j+1])
dfs(j + 1)
t = t[:len(t)-1]
}
}
dfs(0)
return
}
复杂度分析
- 时间复杂度：$O(1)$ 级别的常数时间。段数固定为 4，每段最多 3 种长度，搜索树的叶子不超过 $3^4 = 81$ 个；每条成功路径拼接字符串的开销不超过 $O(12)$。输入长度虽然可达 20，但超过 12 的部分会在前几层就被段数与长度限制截断，规模与
n无关。- 空间复杂度：$O(1)$，递归深度最多 5 层，
t中最多 4 个长度不超过 3 的字符串。返回值按惯例不计入。
关键点总结
- 多条件终止要拆成「成功」与「失败」两个判断分别写：本题必须同时满足「字符用完」和「段数为 4」，把两者合成一个条件或只判其一，都会产出残缺答案。凡是终止条件由多个维度组成的搜索题，都该这样拆。
- 「单调失效」的约束用
break而不是continue：x > 255和前导零一旦成立就不会随着段延长而恢复，break能省掉整段无效枚举。识别约束是「单调」还是「非单调」，是写好剪枝的前提。- 增量维护段的数值而不是反复
parseInt(substring)，既避免了重复建串，也让越界剪枝可以在延伸过程中立刻触发。- 前导零的正确写法是「首字符为 0 且段长大于 1」，不是「首字符为 0」。面试时能主动举出
"0"合法、"01"非法这组对照，说明规则读到位了。- 善用约束反推早停条件：四段最多 12 个字符，所以
n > 12或n < 4时可以直接返回空。哪怕代码里不写这个特判，面试中说出来也是加分项。
易错点总结
- 忘记前导零判断：
s = "010010"会输出"0.10.01.0"这类含"01"的非法结果，答案数量明显多于预期。- 前导零条件写成
s.charAt(i) == '0'而不带i != j：s = "0000"时四个单独的"0"全被否决，本应输出"0.0.0.0"却返回空列表。- 只判
i >= n就收答案：s = "1111"会把只切了 2 段的"11.11"也当成答案输出。- 只判
t.size() == 4就收答案：s = "101023"会输出"1.0.1.0"这种把末尾"23"丢掉的结果。- 漏掉失败条件那一行
if (i >= n || t.size() >= 4) return;：s = "1111"在切满四段后仍继续往下枚举，substring越界抛异常。- 数值判断写成
x >= 255：s = "255255255255"会把合法的"255"段否决，正确答案"255.255.255.255"丢失。- 循环上界写成
j < i + 3而不与n取小：s = "12"时j会取到 2、3，s.charAt(j)越界抛异常。- 递归传
j而不是j + 1：s = "1111"第一段"1"之后又从下标 0 重新开始，字符被重复使用，产出"1.1.1.1"之外还带上无限深的错误路径。- 忘记
t.remove(t.size() - 1)：s = "10203"找到"1.0.20.3"后残留不清，第二个分支会拼出五段甚至更多段的字符串。- 把
x > 255的判断写成continue：s = "9999999999"时每一层都要把三种长度全试一遍，虽然结果仍对，但白白多枚举了必然失败的更长段。- 用正则或
String.split事后校验整个 IP：s = "25525511135"结果虽对，但等于先生成再过滤，既绕过了增量剪枝这个考点，也无法解释「为什么可以break」。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 93. 复原 IP 地址 | 中等 | 与本题完全同题，代码可原样提交 |
| 131. 分割回文串 | 中等 | 同为枚举分割点，段数不固定，合法性判断换成回文且可预处理成表 |
| LCR 086. 分割回文串 | 中等 | 与 131 同题，可对照体会「段数固定」与「段数任意」在终止条件上的差别 |
| 139. 单词拆分 | 中等 | 段的合法性由词典给出，只问能否拆分，退化为一维可达性 DP |
| 140. 单词拆分 II | 困难 | 要求列出全部拆分方案，骨架相同但需记忆化，否则指数级重算 |
| 468. 验证IP地址 | 中等 | 只做判定不做切分，但要同时处理 IPv4 与 IPv6 的完整规则 |
| 306. 累加数 | 中等 | 同样是数字串切分加前导零规则，但段与段之间还有加法关系约束 |