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 地址分量并返回所有合法的复原结果。合法段的约束是长度为 13 个数字数值在 0 到 255 之间不允许前导零但段本身是0时例外01、001均非法。原文明档 articles/restore-ip-addresses.md 在Prerequisites一节中列出了动手前需要具备的三项基础能力Backtracking回溯通过不断做选择、走不通时撤销选择来探索所有可能组合Recursion递归把问题拆解为更小的子问题——每次只放置一个 IP 段String Manipulation字符串操作截取子串并对 IP 段约束做校验。解法一回溯Backtracking直觉合法 IP 地址恰好有 4 个段每段 13 位数字、取值 0255。回溯的核心思路是在字符串中尝试放置 3 个点每一步对当前段取 1、2 或 3 个字符校验其合法性再对剩余部分递归。算法步骤原文档给出的 7 步算法如下若字符串长度超过 12直接返回空列表合法 IP 最多 12 位数字定义递归函数跟踪当前位置i、已放置的段数dots以及正在构建的 IP 字符串curIP基准情形已放满 4 段且恰好消耗完整个字符串把该 IP 加入结果每次调用中从当前位置出发尝试取 1、2、3 个字符作为当前段跳过带前导零的段除非该段就是0以及数值 ≥ 256 的段以新的位置、加一后的段数、更新后的 IP 字符串递归返回所有找到的合法 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() 255typescript/0093-restore-ip-addresses.ts 与 javascript/0093-restore-ip-addresses.jsJavaScript 版本甚至用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 次尝试是常数上界。算法步骤若字符串长度超过 12返回空列表四个嵌套循环各自从 1 迭代到 3代表四段的长度seg1seg4若四段长度之和 ≠ 字符串长度跳过该组合按当前长度切出四个子串逐段校验无前导零单字符除外且数值 ≤ 255四段全部合法则用点连接后加入res返回结果。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:s1s2] num3 s[s1s2:s1s2s3] num4 s[s1s2s3:] 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 ListString restoreIpAddresses(String s) { ListString 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 4IP 恰好 4 个段。代入后时间复杂度是 O(3⁴ · n) O(81n)即常数因子 81 乘以线性因子 n81 次回溯中被剪枝后实际更少尝试每次处理至多 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:j1]) 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.csif (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会形成 256259截断。另外该实现用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 题在仓库中的实际实现分布如下语言文件实现风格C#csharp/0093-restore-ip-addresses.cs回溯 增量数值累积 StringBuilder 回滚Gogo/0093-restore-ip-addresses.go回溯闭包递归JavaScriptjavascript/0093-restore-ip-addresses.js回溯Kotlinkotlin/0093-restore-ip-addresses.kt回溯局部函数Rustrust/0093-restore-ip-addresses.rs回溯关联函数递归TypeScripttypescript/0093-restore-ip-addresses.ts回溯而 articles/restore-ip-addresses.md 文档本身在两种解法下额外收录了 Python、Java、C、Swift 等更多语言的完整代码回溯解法含 Python/Java/C/JS/C#/Go/Kotlin/Swift/Rust 共 9 个 Tab枚举解法同样 9 个 Tab可作为跨语言对照学习的完整材料。小结0093 的核心是把「插入 3 个点」建模为「每段取 13 位并逐段校验」回溯与枚举只是同一搜索树的两种遍历方式回溯以递归天然支持逐层剪枝枚举以 81 次常数级尝试换取无递归开销。两条实现红线必须守住——单字符零放行、多字符零拒绝的前导零判定以及 255 上界检查入口处的长度预判12 直接空返回C# 版还补了 4 的预判则保证无解输入不浪费搜索。掌握这套「约束分割 逐段校验」的范式后同类问题如分割数字串为若干合法 token都可以按相同模板套用。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考