复原 IP 地址如何用回溯处理分段、前导零和范围校验？

简化版

复原 IP 地址就是把字符串切成 4 段，每段长度 1 到 3，数值必须在 0 到 255，且不能有非法前导零。回溯状态记录当前下标和已切出的段，段数为 4 且正好用完字符串时收集答案。

详细版

核心状态是 dfs(index, parts)：index 表示下一段从字符串哪里开始，parts 保存已切出的 IP 段。每一层尝试长度 1..3 的子串，若子串越界、前导零非法、数值大于 255，就跳过或停止。

剪枝可以从剩余长度入手：还需要 remainParts = 4 - parts.size() 段，每段至少 1 位、最多 3 位，所以剩余字符数必须满足 remainParts <= remainingChars <= 3 * remainParts。不满足时直接返回。

复杂度很小，因为 IP 固定只有 4 段，每段最多 3 种长度，最多尝试 3^4 = 81 条切分路径。

完整版教学

一、题目本质是“切分型回溯”

输入 s = "25525511135"，输出可以是：

255.255.11.135
255.255.111.35

这类题不是在每个字符上选或不选，而是在当前位置决定“下一刀切多长”。IP 地址固定 4 段，每段长度只能是 1、2、3，因此搜索树非常窄。

index=0
├─ 取 1 位
├─ 取 2 位
└─ 取 3 位

二、合法 IP 段有三个条件

每一段必须同时满足：

条件	说明	示例
长度 1 到 3	IPv4 每段最多三位十进制数	`1`、`25`、`255`
数值 0 到 255	超过 255 非法	`256` 非法
无非法前导零	长度大于 1 时不能以 0 开头	`0` 合法，`01` 非法

前导零是面试最容易漏的点。"010010" 的合法结果中可以有 0.10.0.10，但不能有 0.100.1.0 之外的 01 这种段。

记忆钩子：IP 段先看长度，再看前导零，最后看数值；三个门都过了才递归。

三、状态设计：index 和 parts

回溯函数可以写成 dfs(index, parts)：

index：下一段从 s[index] 开始切
parts：已经切出的段，例如 ["255", "255"]

终止条件有两个维度：段数和字符是否用完。只有 parts.size() == 4 && index == s.length() 才是合法答案；段数到 4 但字符串没用完，或者字符串用完但段数不足 4，都不合法。

四、剩余长度剪枝怎么推

假设还需要 remainParts 段，剩余字符数是 remainingChars。每段至少 1 个字符，所以 remainingChars 不能小于 remainParts；每段最多 3 个字符，所以不能大于 3 * remainParts。

remainParts <= remainingChars <= 3 * remainParts

例如字符串剩余 7 个字符，但只剩 2 段可切，最多能容纳 6 个字符，当前分支必然失败。这个剪枝可以放在每次进入递归函数的开头。

五、代码模板

List<String> restoreIpAddresses(String s) {
    List<String> res = new ArrayList<>();
    dfs(s, 0, new ArrayList<>(), res);
    return res;
}

void dfs(String s, int index, List<String> parts, List<String> res) {
    int remainParts = 4 - parts.size();
    int remainingChars = s.length() - index;
    if (remainingChars < remainParts || remainingChars > remainParts * 3) return;

    if (parts.size() == 4) {
        if (index == s.length()) res.add(String.join(".", parts));
        return;
    }

    for (int len = 1; len <= 3 && index + len <= s.length(); len++) {
        String part = s.substring(index, index + len);
        if (part.length() > 1 && part.charAt(0) == '0') break;
        int value = Integer.parseInt(part);
        if (value > 255) break;
        parts.add(part);
        dfs(s, index + len, parts, res);
        parts.remove(parts.size() - 1);
    }
}

这里两个 break 都有依据：长度继续增加时，前导零问题不会消失；数值超过 255 后，再取更长只会更大。

六、用样例走一遍

以 s = "101023" 为例：

1 | 0 | 10 | 23  -> 1.0.10.23
1 | 0 | 102 | 3  -> 1.0.102.3
10 | 1 | 0 | 23  -> 10.1.0.23
10 | 10 | 2 | 3  -> 10.10.2.3
101 | 0 | 2 | 3  -> 101.0.2.3

像 1 | 010 | 2 | 3 会因为 010 有前导零被剪掉；像 101 | 023 这种段同样非法。

七、常见误区与追问

误区：只判断数值小于 255。 01 的数值是 1，但作为 IP 段非法。
误区：段数到 4 就直接收集。 必须同时满足字符串刚好用完。
误区：字符串用完就直接收集。 还要检查是否已经切出 4 段。
追问：为什么复杂度可以看作常数？ 因为 IPv4 固定 4 段，每段最多尝试 3 种长度，搜索上限很小。
追问：剪枝条件怎么记？ 剩余字符必须能被剩余段数装下，即每段 1 到 3 位。
追问：为什么 value > 255 后可以 break？ 当前位数继续增加只会让十进制数更大，不可能重新合法。

八、加强记忆

复原 IP 地址要记成“固定 4 段的切分回溯”：每层不是选择某个元素，而是选择下一段切 1、2、3 位。判断合法段按“长度、前导零、数值范围”三步走，终止条件按“4 段且刚好用完”双条件判断，剪枝按剩余字符能否放进剩余段数来推。这样答题时既能写出代码，也能解释每个 return 和 break 的原因。

简化版

详细版