企业官网建设流程全解析

leetcode 0093 Restore IP Addresses：回溯与枚举两种解法的完整实现、复杂度分析与常见陷阱

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文围绕 LeetCode 0093「Restore IP Addresses（复原 IP 地址）」问题，基于 leetcode 仓库中的解题文档 articles/restore-ip-addresses.md 及其配套的多语言源码，系统讲解两种核心解法——回溯（Backtracking）与四重循环枚举（Iteration）的完整实现、剪枝策略与时间空间复杂度，并结合 rust/0093-restore-ip-addresses.rs、csharp/0093-restore-ip-addresses.cs 等仓库源码剖析增量数值累积等实现细节。读完本文，你将掌握带约束的字符串分割类问题的通用建模方法、逐段校验的标准写法，以及避免前导零、上界检查、长度预判等三类典型 Bug 的具体手段。

问题定义与前置知识

给定一个只包含数字的字符串，需要向其中插入 3 个点，把字符串切分成 4 个段（segment），使得每一段都是合法的 IPv4 地址分量，并返回所有合法的复原结果。合法段的约束是：

• 长度为 1～3 个数字；
• 数值在 0 到 255 之间；
• 不允许前导零，但段本身是"0"时例外（"01"、"001"均非法）。

原文明档 articles/restore-ip-addresses.md 在Prerequisites一节中列出了动手前需要具备的三项基础能力：

• Backtracking（回溯）：通过不断做选择、走不通时撤销选择来探索所有可能组合；
• Recursion（递归）：把问题拆解为更小的子问题——每次只放置一个 IP 段；
• String Manipulation（字符串操作）：截取子串并对 IP 段约束做校验。

解法一：回溯（Backtracking）

直觉

合法 IP 地址恰好有 4 个段，每段 1～3 位数字、取值 0～255。回溯的核心思路是：在字符串中尝试放置 3 个点，每一步对当前段取 1、2 或 3 个字符，校验其合法性，再对剩余部分递归。

算法步骤

原文档给出的 7 步算法如下：

1. 若字符串长度超过 12，直接返回空列表（合法 IP 最多 12 位数字）；
2. 定义递归函数，跟踪当前位置i、已放置的段数dots以及正在构建的 IP 字符串curIP；
3. 基准情形：已放满 4 段且恰好消耗完整个字符串，把该 IP 加入结果；
4. 每次调用中，从当前位置出发尝试取 1、2、3 个字符作为当前段；
5. 跳过带前导零的段（除非该段就是"0"）以及数值 ≥ 256 的段；
6. 以新的位置、加一后的段数、更新后的 IP 字符串递归；
7. 返回所有找到的合法 IP。

Python 参考实现

以下是原文档中完整的 Python 回溯实现，可直接复制到 LeetCode 题解框架中运行：

class Solution: def restoreIpAddresses(self, str_: str) -> List[str]: res = [] s = str_ if len(s) > 12: return res def backtrack(i, dots, curIP): if dots == 4 and i == len(s): res.append(curIP[:-1]) return if dots > 4: return for j in range(i, min(i + 3, len(s))): if i != j and s[i] == "0": continue if int(s[i: j + 1]) < 256: backtrack(j + 1, dots + 1, curIP + s[i: j + 1] + ".") backtrack(0, 0, "") return res

（注：为规避参数名s与外部变量重名，上面把入参命名为str_；原文档使用s: str，语义完全一致。）

几个关键细节值得注意：

• dots == 4 and i == len(s)是双重条件：不仅段数放满，字符串也必须被完整消耗，否则会出现192.168.0.1只剩尾巴没吃掉、或字符串没切完却凑齐 4 段的非法结果；
• i != j and s[i] == "0"一条语句同时处理了前导零：i != j表示当前段长度大于 1，此时若首位是0就直接continue，单字符的"0"自然放行；
• curIP以带尾点的形式传递（如"192.168.0."），命中基准情形时curIP[:-1]去掉最后一个点即可，避免了 join 操作。

仓库多语言源码中的同一模式

leetcode 仓库 README.md 的完成情况表格（0093 一行）显示，该题在仓库中收录了 C#、Go、JavaScript、Kotlin、Rust、TypeScript 六种语言的解法。通读这些源码后可以确认，它们与原文档的回溯算法完全同构，且共享同一个剪枝谓词——「段值 < 256 且（单字符 或 首位非零）」：

• rust/0093-restore-ip-addresses.rs：循环for j in i..usize::min(i + 3, s.len())，校验条件写作val < 256 && (i == j || s.get(i..i + 1).unwrap() != "0")，与 Python 版逐行对应；
• go/0093-restore-ip-addresses.go：用闭包var backtrack func(i, dots int, currentIP string)承载递归（Go 无匿名函数自引用的类语法），校验条件为val < 256 && (i == j || s[i] != '0')；
• kotlin/0093-restore-ip-addresses.kt：把上界写成等价的digits.toInt() <= 255；
• typescript/0093-restore-ip-addresses.ts 与 javascript/0093-restore-ip-addresses.js：JavaScript 版本甚至用+s.slice(i, j + 1)一元加号替代parseInt做强制转换，逻辑不变。

这些源码印证了一个结论：只要剪枝谓词写成(i == j || s[i] != '0') && val <= 255这一形式，任意语言的翻译都能保持正确性，这也是该题跨语言实现中唯一需要格外小心的地方。

解法二：四重循环枚举（Iteration）

直觉

由于恰好有 4 个段、每段长度只能是 1、2 或 3，段的长度组合总共只有 3⁴ = 81 种。与其递归，不如直接用四个嵌套循环枚举所有长度组合(seg1, seg2, seg3, seg4)，对每个组合检查四段长度之和是否等于输入串长，再逐段校验。这样完全避免了递归开销，且 81 次尝试是常数上界。

算法步骤

1. 若字符串长度超过 12，返回空列表；
2. 四个嵌套循环各自从 1 迭代到 3，代表四段的长度seg1～seg4；
3. 若四段长度之和 ≠ 字符串长度，跳过该组合；
4. 按当前长度切出四个子串；
5. 逐段校验：无前导零（单字符除外）且数值 ≤ 255；
6. 四段全部合法则用点连接后加入res；
7. 返回结果。

Python 实现

原文档中的完整 Python 枚举实现如下：

class Solution: def restoreIpAddresses(self, s: str) -> List[str]: res = [] if len(s) > 12: return res def valid(num): return len(num) == 1 or (int(num) < 256 and num[0] != "0") def add(s1, s2, s3, s4): if s1 + s2 + s3 + s4 != len(s): return num1 = s[:s1] num2 = s[s1:s1+s2] num3 = s[s1+s2:s1+s2+s3] num4 = s[s1+s2+s3:] if valid(num1) and valid(num2) and valid(num3) and valid(num4): res.append(num1 + "." + num2 + "." + num3 + "." + num4) for seg1 in range(1, 4): for seg2 in range(1, 4): for seg3 in range(1, 4): for seg4 in range(1, 4): add(seg1, seg2, seg3, seg4) return res

注意valid的写法：len(num) == 1 or (int(num) < 256 and num[0] != "0")——单字符无条件合法；多字符时才检查首位非零与上界。

Java 实现

public class Solution { public List<String> restoreIpAddresses(String s) { List<String> res = new ArrayList<>(); if (s.length() > 12) return res; for (int seg1 = 1; seg1 < 4; seg1++) { for (int seg2 = 1; seg2 < 4; seg2++) { for (int seg3 = 1; seg3 < 4; seg3++) { for (int seg4 = 1; seg4 < 4; seg4++) { if (seg1 + seg2 + seg3 + seg4 != s.length()) continue; String num1 = s.substring(0, seg1); String num2 = s.substring(seg1, seg1 + seg2); String num3 = s.substring(seg1 + seg2, seg1 + seg2 + seg3); String num4 = s.substring(seg1 + seg2 + seg3); if (isValid(num1) && isValid(num2) && isValid(num3) && isValid(num4)) { res.add(num1 + "." + num2 + "." + num3 + "." + num4); } } } } } return res; } private boolean isValid(String num) { if (num.length() > 1 && num.charAt(0) == '0') return false; int value = Integer.parseInt(num); return value <= 255; } }

原文档中还给出了该解法的 C++、JavaScript、C#、Go、Kotlin、Swift、Rust 版本，结构完全一致（四个for循环 +isValid校验），此处不再逐一重复；回溯解法的 C++/JavaScript/C#/Go/Kotlin/Swift/Rust 版本同理，均在 articles/restore-ip-addresses.md 中以语言 Tab 形式收录。

复杂度分析

原文档对两种解法给出相同的大 O 结论：

• 时间复杂度：O(mⁿ · n)
• 空间复杂度：O(m · n)

其中 m = 3（每个段至多 3 位数字），n = 4（IP 恰好 4 个段）。代入后时间复杂度是 O(3⁴ · n) = O(81n)，即常数因子 81 乘以线性因子 n：81 次（回溯中被剪枝后实际更少）尝试，每次处理至多 12 个字符。空间上递归深度至多 4 层，每层持有一个长度不超过 12 的字符串，故为 O(m · n) 的常数级开销。可以这样理解：无论输入如何变化，两种解法都在常数次枚举内完成搜索，差别只在于递归调用的额外开销与剪枝的提前程度——回溯在深入前就能砍掉非法分支，而枚举必须完整走完 81 个组合再逐个否决。

常见陷阱（Common Pitfalls）

原文档Common Pitfalls一节归纳了三类高频错误，这里完整继承并补充对照代码定位：

陷阱一：允许多位段带前导零

"01"、"001"这类段在 IP 地址中非法，但单独的"0"合法。校验逻辑必须精确区分这两种情况：拒绝所有「长度 > 1 且首位为 0」的段，同时放行单字符零。回溯版中的if i != j and s[i] == "0": continue、枚举版中的len(num) == 1 or (… and num[0] != "0")就是为这个区分而写的。

陷阱二：漏掉段的数值上界检查

每段必须 ≤ 255。原文档特别提醒：忘记检查该约束，或在边界上使用< 256与<= 255混写（两者其实等价，真正的风险是漏检），都会让"256"这类三位段蒙混过关。回溯解法里int(s[i:j+1]) < 256与枚举解法里value <= 255必须出现在每一次取段之后，而不是只在长度为 3 时检查——两位段虽然必然 ≤ 99，但统一的校验更不易出错。

陷阱三：不做输入长度的提前判断

合法 IP 的数字位数上限是 4 段 × 3 位 =12 位，下限是 4 段 × 1 位 =4 位。超过 12 位时必然无解，应在搜索前直接返回空列表；所有语言的参考实现都在函数入口做了len(s) > 12的提前退出。仓库中的 C# 解法还额外展示了下限判断——csharp/0093-restore-ip-addresses.cs 第一行即为if (s.Length < 4) return [];，长度不足 4 位同样无解。这两处提前返回虽然对大 O 无影响，却能避免在无解输入上白跑一遍搜索树。

源码纵深：C# 实现的增量数值累积与提前截断

仓库中的 C# 解法 csharp/0093-restore-ip-addresses.cs 提供了一个与其他语言实现明显不同的工程细节，值得单独剖析。它没有像其他实现那样每次取子串再int.Parse，而是把当前段的数值当作整数增量累积，并借此在非法前缀出现的第一时间break整个候选循环（csharp/0093-restore-ip-addresses.cs）：

if (octet.HasValue) { if (octet.Value == 0 || octet > 25 || octet == 25 && input[i] > '5') break; octet *= 10; octet += input[i] - '0'; }

这段逻辑等价于「逐位读入，一旦不可能变成合法段就停止扩展」：

• octet.Value == 0：当前段前缀已经是"0"，再拼任何一位都会产生前导零，截断；
• octet > 25：前缀已大于 25（如"26"），后面再拼一位必然 ≥ 260 > 255，截断；
• octet == 25 && input[i] > '5'：前缀恰好是 25 且下一位超过'5'，会形成 256～259，截断。

另外该实现用StringBuilder加sb.Remove(sb.Length - octet_string.Length, octet_string.Length)做回溯撤销（csharp/0093-restore-ip-addresses.cs），对应 Rust 版中cur_ip.truncate(prev_len)的「记录旧长度、递归后回滚」模式（原文档 Rust 代码中的prev_len/truncate即此写法），而 Python/Go/Kotlin 等版本由于字符串不可变，直接以参数传递新串完成「撤销」。从源码结构看，这三种撤销策略——传新串、Builder 回滚、Vec 截断——分别是动态语言、C 系语言、Rust 在不可变/可变字符串上的自然选择，算法语义完全一致。

仓库实现索引

基于 README.md 完成情况表格与源码目录核对，0093 题在仓库中的实际实现分布如下：

而 articles/restore-ip-addresses.md 文档本身在两种解法下额外收录了 Python、Java、C++、Swift 等更多语言的完整代码（回溯解法含 Python/Java/C++/JS/C#/Go/Kotlin/Swift/Rust 共 9 个 Tab，枚举解法同样 9 个 Tab），可作为跨语言对照学习的完整材料。

小结

0093 的核心是把「插入 3 个点」建模为「每段取 1～3 位并逐段校验」，回溯与枚举只是同一搜索树的两种遍历方式：回溯以递归天然支持逐层剪枝，枚举以 81 次常数级尝试换取无递归开销。两条实现红线必须守住——单字符零放行、多字符零拒绝的前导零判定，以及 255 上界检查；入口处的长度预判（>12 直接空返回，C# 版还补了 <4 的预判）则保证无解输入不浪费搜索。掌握这套「约束分割 + 逐段校验」的范式后，同类问题（如分割数字串为若干合法 token）都可以按相同模板套用。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode