#93. 复原 IP 地址

• LeetCode：93. 复原 IP 地址 · LCR 087. 复原 IP 地址
• 难度：中等
• 归类：字符串、回溯
• 主解法：回溯枚举分段位置 + 合法性剪枝

#先给结论

目标是给数字字符串插入 3 个点，将它切成恰好 4 个合法字段。每个字段必须满足：

• 长度为 1～3。
• 数值在 0～255 之间。
• 除了单独的 "0"，不能以 "0" 开头。

回溯时维护「当前读取位置」和「已经选择的字段」，每层枚举下一段的 1～3 位。遇到非法字段就 break，当前分支不再往下展开。

#题目描述

给定一个只包含数字的字符串 s，在不重排、不删除任何数字的前提下插入 3 个 .，返回所有可能的有效 IPv4 地址。答案可以按任意顺序返回。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135", "255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：[
  "1.0.10.23",
  "1.0.102.3",
  "10.1.0.23",
  "10.10.2.3",
  "101.0.2.3"
]

两道题的长度约束不同：

• 93 题：1 <= s.length <= 20。
• LCR 087：0 <= s.length <= 3000。

由于有效 IPv4 地址去掉点后只能包含 4～12 位数字，长度不在这个范围内时可以直接返回空数组。

#合法字段的判断

一个字段合法，当且仅当同时满足：

1. 字段非空，长度不超过 3。
2. 如果长度大于 1，首字符不能是 "0"。
3. 数值不超过 255。

例如：

#回溯设计

递归函数 dfs(start, path) 中：

• start 表示下一段从 s[start] 开始。
• path 保存已经确定的字段数组（如 ["255", "255"]）。
• result 保存所有完整且合法的 IP 地址。

每次递归入口都满足以下不变量：

• path 中的每个字段都合法。
• path.join('') 恰好等于 s.slice(0, start)。
• path.length <= 4。

因此，当 path 恰好有 4 段并且 start === s.length 时，才能加入答案。

#为什么选择「扩展运算符」传递 path

由于 path 最多只有 4 个短字符串，拷贝代价可以忽略。用 [...path, seg] 代替 push/pop 的好处是：

• 不需要关心回溯后的「恢复现场」；
• 每层递归拿到的是独立的 path，逻辑更纯粹；
• 避免遗忘 pop() 导致的分支污染。

如果面试官追问，也可以改回 push/pop 以展示对回溯状态恢复的理解。

#剪枝规则

#越界剪枝

dfs 的 for 循环只枚举字段长度 len = 1, 2, 3。一旦 start + len > s.length，说明剩余字符不足以支撑当前长度，直接 break。

#前导零剪枝

如果当前字段的第一个字符是 "0"，只有单字符 "0" 合法。更长的候选都会保留前导零，因此可以直接 break。

#数值上界剪枝

同一个起点下，字段从 1 位扩展到 3 位时数值只会增大。一旦数值超过 255，继续增加数字也不可能重新合法，可以 break。

#为什么不需要「剩余字符数量剪枝」

IPv4 固定 4 段、每段最多 3 位，搜索树深度最多 4、分支因子最多 3。即便输入长度达到 3000，有效的递归调用也只有几十次，因此不必像通用回溯那样显式计算 remainingChars 来做范围剪枝。

#示例推演

以 s = "010010" 为例：

其他分支会因为越界、前导零或字段数值超过 255 被剪掉。

最终结果：

["0.10.0.10", "0.100.1.0"]

#代码实现

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
    const result = [];

    const dfs = (start, path) => {
        if (path.length === 4) {
            if (start === s.length) {
                result.push(path.join('.'));
            }
            return;
        }

        for (let len = 1; len <= 3; len++) {
            if (start + len > s.length) break;

            const seg = s.slice(start, start + len);
            if (!valid(seg)) break;

            dfs(start + len, [...path, seg]);
        }
    };

    dfs(0, []);
    return result;
};

function valid(str) {
    if (str[0] === '0') return str.length === 1;
    return +str <= 255;
}

#代码与思路对照

#正确性说明

可以从「生成的答案都合法」和「不会漏掉合法答案」两方面证明。

#生成的答案都合法

加入 path 的字段都通过了 valid() 检查（长度天然在 1～3 内、无前导零、数值不超过 255）。算法只有在 path 恰好包含 4 段且所有字符都被使用时才记录结果，因此生成的每个字符串都是合法 IPv4 地址。

#不会漏掉合法答案

任意合法 IPv4 地址都由 4 个长度为 1～3 的合法字段组成。DFS 会从每个字段起点依次尝试长度 1、2、3，因此一定会枚举到该地址的四个字段。

被剪掉的分支只可能是：

• 字段存在前导零；
• 字段数值超过 255；
• 剩余字符不足以放下当前枚举长度（start + len > s.length）。

这些情况都不可能属于合法答案，所以剪枝不会漏解。

#边界与陷阱

• 长度不在 4～12： 不可能组成 4 个字段，算法会在根节点快速结束，返回空数组。
• 全零字符串： "0000" 只能得到 "0.0.0.0"。
• 前导零： "010010" 中可以选择 "0"，但不能选择 "01" 或 "010"。
• 数值边界： "255" 合法，"256" 非法。
• 必须恰好四段： 不能只判断字符串是否用完，也不能选择完四段后继续递归。
• 必须使用全部字符： 四段合法但仍有剩余字符时不能记录答案。
• 答案顺序： 题目允许按任意顺序返回，不需要额外排序。

#复杂度分析

IPv4 固定为 4 段，每段最多尝试 3 种长度，因此搜索树的状态数存在与输入长度无关的常数上界：

1 + 3 + 3² + 3³ + 3⁴

每次只处理至多 3 个字符。由于 4 和 3 都是 IPv4 的固定常数，也可以记为：

• 时间复杂度：O(1)。
• 额外空间复杂度：O(1)，不计返回结果。

长度超过 12 的输入仍会以常数时间结束，因为递归深度被字段数限制在 4 层。

#面试官递进追问

#1. 为什么本题适合回溯？

三个点的位置存在多种选择，而每次选择都会影响后续剩余字符。回溯可以枚举每一段的长度，并在发现当前前缀不可能形成合法 IP 时立即停止。

#2. 递归函数需要维护哪些状态？

只需要当前读取位置 start 和已经选择的字段 path。原字符串和答案数组在闭包中共享，不需要为每层复制剩余字符串。

#3. 用push/pop 和用[...path, seg] 有什么区别？

push/pop 复用同一个数组，需要手动恢复现场，空间更省；[...path, seg] 每层创建新数组，逻辑更纯粹，不用担心遗忘 pop()。本题中 path 极短，两种写法都可以接受。

#4. 为什么遇到前导零后可以直接break？

当字段以 "0" 开头时，只有单字符 "0" 合法。更长的候选都会保留这个前导零，因此都不合法，可以停止当前起点的后续枚举。

#5. 为什么字段数值超过 255 后也可以break？

当前字段只包含数字，继续在右侧添加数字不会让它重新落回 0～255，所以更长候选同样非法。

#6. 为什么结束条件要同时检查字段数和字符串位置？

只有「恰好 4 段」和「恰好用完所有字符」同时满足才是完整地址。缺少任一条件，都可能接受三段地址或仍有字符残留的错误结果。

#7. 为什么复杂度可以写成O(1)？

IPv4 的字段数固定为 4，每段长度固定不超过 3，搜索状态数量存在与输入长度无关的常数上界。

#8. 不用回溯还能怎么做？

可以枚举三个点的位置 i < j < k，分别验证 s[0..i)、s[i..j)、s[j..k) 和 s[k..n)。本质上仍是在枚举所有切分位置，代码可能更直接，但字段合法性判断不能省略。

#常见错误

• 把 "0" 和含前导零的 "00"、"01" 混为一谈。
• 只限制字段长度，没有检查数值是否超过 255。
• 已选 4 段后仍继续递归，产生无意义的更深搜索。
• 字符串用完就记录答案，却没有检查是否恰好得到 4 段。
• 使用共享的 path 配合 push/pop 后忘记 pop()，污染其他递归分支。

#可迁移总结

• 分割类回溯： 状态通常是当前位置和已经选择的片段。
• 单调剪枝： 候选继续扩展只会更坏时，可以使用 break，不必只跳过当前候选。
• 不可变路径： 小规模路径数组可以考虑用扩展运算符传递，降低心智负担。
• 一句话记忆： 枚举每段 1～3 位，同时剪掉越界、前导零和大于 255 的分支。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 为什么 valid() 里不需要显式判断 str.length > 3？

2. 输入 "0000" 时，为什么每一层都只能选择一位？

3. 如果只检查 path.length === 4，却不检查 start === s.length，会接受什么错误结果？

4. 尝试把 [...path, seg] 改回 push/pop 写法，并说明两者的优劣。