教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文基于「算法通关手册」仓库中的 restore-ip-addresses.md 题解文档整理而成结合 回溯算法基础讲解 及仓库内同名变体题解 LCR 087. 复原 IP 地址 进行源码级扩充。你将掌握有效 IP 地址的判定规则、用「选择-递归-撤销」三步走实现回溯的思路、剪枝优化的两种写法以及复杂度分析的严谨推导。1. 题目概述题目编号0093. 复原 IP 地址标签字符串、回溯难度中等1.1 题目链接0093. 复原 IP 地址 - 力扣LeetCode1.2 题目大意描述给定一个只包含数字的字符串s用来表示一个 IP 地址。要求返回所有由s构成的有效 IP 地址这些地址可以通过在s中插入.来形成。不能重新排序或删除s中的任何数字。可以按任何顺序返回答案。说明有效 IP 地址正好由四个整数每个整数由 $0 \sim 255$ 的数构成且不能含有前导 0整数之间用.分割。$1 \le s.length \le 20$。s仅由数字组成。示例示例 1输入s 25525511135 输出[255.255.11.135,255.255.111.35]示例 2输入s 0000 输出[0.0.0.0]关于这道题在仓库中的收录情况该题同时出现在 题解总列表、面试 100 题列表、面试 200 题列表 以及 回溯算法题目分类列表 中是算法面试中字符串与回溯结合的高频考点。力扣官方还提供了等价变体题LCR 087. 复原 IP 地址其题解见 docs/solutions/LCR/0on3uN.md。2. 解题思路回溯算法一个有效 IP 地址由四个整数构成中间用 $3$ 个点隔开。现在给定的是无分隔的整数字符串我们可以通过在整数字符串中间的不同位置插入 $3$ 个点来生成不同的 IP 地址。这个过程可以通过回溯算法来生成。本题与 0078. 子集、0046. 全排列 等题一样本质上是「组合型」回溯在字符串的 $|s|-1$ 个间隔位置中选择 $3$ 个位置插入.把字符串切分成 $4$ 段。由于每段必须是 $0 \sim 255$ 之间的合法整数且不能有前导 0因此候选切割方案非常有限。2.1 回顾回溯算法三步走仓库中 回溯算法基础 一节给出了回溯算法的通用方法论通过深度优先搜索不断尝试所有可能的选择当发现当前路径不满足条件时就回退回溯尝试其他路径最终找到所有可行解。其基本步骤如下明确所有选择画出决策树理清每一步有哪些可选项。每个节点的分支代表一次选择。明确终止条件终止条件通常是递归到某一深度、遍历完所有元素或满足题目要求。到达终止条件时处理当前结果如加入答案集。将决策树和终止条件转化为代码定义回溯函数明确函数意义、传入参数、返回结果等书写回溯函数主体给出约束条件、选择元素、递归搜索、撤销选择部分明确递归终止条件给出递归终止条件以及递归终止时的处理方法。通用模板为def backtrack(参数): if 终止条件: 处理结果 return for 选择 in 可选列表: if 满足约束: 做选择 backtrack(新参数) 撤销选择下面严格按这三步走分析复原 IP 地址问题。2.2 明确所有选择对于当前的剩余子串我们要切割出一个合法的 IP 子段。因为 IP 地址每一段的取值范围是 $0 \sim 255$最多 3 位数字所以当前段的起点只能是index终点i只能取index、index 1、index 2即最多枚举 3 种子段长度。这正是本题回溯分支数量被限制在 $O(3^4)$ 的根本原因——决策树每一层最多 3 个分支整棵树深度最多 4 层。2.3 明确终止条件当遍历到决策树的叶子节点时就终止了即当前路径搜索到末尾时递归终止。具体到本题当存放当前结果的数组path的长度等于 $4$并且剩余字符开始位置为字符串结束位置即len(path) 4 and index len(s)时说明已经切出 4 段且用完了所有字符递归停止将当前结果加入答案如果回溯过程中切割次数大于 4即len(path) 4说明已经超出了 IP 地址应有的段数递归停止直接返回。2.4 将决策树和终止条件翻译成代码1. 定义回溯函数backtracking(index)函数的传入参数是index剩余字符开始位置全局变量是res存放所有符合条件结果的集合数组和path存放当前符合条件的结果。backtracking(index)函数代表的含义是递归从index位置开始从剩下字符中选择当前子段的值。2. 书写回溯函数主体给出选择元素、递归搜索、撤销选择部分从当前正在考虑的字符index到字符串结束为止枚举出所有可作为当前子段值的字符。对于每一个子段值约束条件只能从index位置开始选择并且要符合规则要求数值在 $0 \sim 255$ 之间、无前导 0选择元素将其添加到当前子段数组path中递归搜索在选择该子段值的情况下继续递归从剩下字符中选择下一个子段值撤销选择将该子段值从当前结果数组path中移除。for i in range(index, len(s)): # 枚举可选元素列表 sub s[index: i 1] # 如果当前值不在 0 ~ 255 之间直接跳过 if int(sub) 255: continue # 如果当前值为 0但不是单个 000...直接跳过 if int(sub) 0 and i ! index: continue # 如果当前值大于 0但是以 0 开头0XX...直接跳过 if int(sub) 0 and s[index] 0: continue path.append(sub) # 选择元素 backtracking(i 1) # 递归搜索 path.pop() # 撤销选择3. 明确递归终止条件给出递归终止条件以及递归终止时的处理方法当遍历到决策树的叶子节点时就终止了。也就是存放当前结果的数组path的长度等于 $4$并且剩余字符开始位置为字符串结束位置即len(path) 4 and index len(s)时递归停止如果回溯过程中切割次数大于 4即len(path) 4递归停止直接返回。2.5 三条合法性剪枝规则详解上述代码中的三条continue剪枝是本题的核心缺一不可逐一说明剪枝条件拦截的非法子段示例int(sub) 255数值超出 $0 \sim 255$ 范围256、999int(sub) 0 and i ! index值为 0 但长度大于 1前导 000、000int(sub) 0 and s[index] 0值大于 0 却以 0 开头前导 001、023三条规则共同保证了「不能含有前导 0」的判定数字0只能以单个0的形式出现而01、00这类子段一律拒绝。在时间约束下这三条规则也保证了决策树的每个节点最多只有 3 个合法分支因为长度超过 3 的子段必然 255在枚举到i index 2之后就会被int(sub) 255剪掉。3. 完整代码实现class Solution: def restoreIpAddresses(self, s: str) - List[str]: res [] path [] def backtracking(index): # 如果切割次数大于 4直接返回 if len(path) 4: return # 切割完成将当前结果加入答案结果数组中 if len(path) 4 and index len(s): res.append(..join(path)) return for i in range(index, len(s)): sub s[index: i 1] # 如果当前值不在 0 ~ 255 之间直接跳过 if int(sub) 255: continue # 如果当前值为 0但不是单个 000...直接跳过 if int(sub) 0 and i ! index: continue # 如果当前值大于 0但是以 0 开头0XX...直接跳过 if int(sub) 0 and s[index] 0: continue path.append(sub) backtracking(i 1) path.pop() backtracking(0) return res3.1 代码运行验证对题目给出的示例以及一个扩展用例运行上述实现已在本地 Python 3 环境中实测验证 Solution().restoreIpAddresses(25525511135) [255.255.11.135, 255.255.111.35] Solution().restoreIpAddresses(0000) [0.0.0.0] Solution().restoreIpAddresses(101023) [1.0.10.23, 1.0.102.3, 10.1.0.23, 10.10.2.3, 101.0.2.3]可以看到25525511135恰好得到题面给出的两种答案0000因为前导 0 规则的限制只能切分成0.0.0.0一种方案其余如0.00.0.0均被剪枝101023得到 5 种合法 IP覆盖了多种切割组合验证了回溯对全解空间的穷举能力。3.2 递归执行过程速览以 s 25525511135 为例第 1 层index 0候选子段为2、25、2552552因int 255被剪枝第 2 层例如已选255后从index 3继续候选为2、25、255第 3 层继续从下一个index枚举 3 种子段第 4 层当len(path)达到 4 且index len(s)时将..join(path)写入res并返回每层递归返回后执行path.pop()撤销当前子段恢复现场以尝试下一个分支。由于每层最多 3 个分支、最多 4 层搜索树规模极小无需额外的记忆化或动态规划优化即可通过全部测试用例。4. 复杂度分析时间复杂度$O(3^4 \times |s|)$其中 $|s|$ 是字符串s的长度。由于 IP 地址的每一子段位数不会超过 $3$因此在递归时我们最多只会深入到下一层中的 $3$ 种情况。而 IP 地址由 $4$ 个子段构成所以递归的最大层数为 $4$ 层则递归的时间复杂度为 $O(3^4)$。而每次将有效的 IP 地址添加到答案数组的时间复杂度为 $|s|$所以总的时间复杂度为 $3^4 \times |s|$。空间复杂度$O(|s|)$只记录除了用来存储答案数组之外的空间复杂度。递归栈深度不超过 4 层加上path与字符串切片sub的存储空间开销与字符串长度线性相关。4.1 复杂度分析的严谨性说明从代码结构看for i in range(index, len(s))表面上似乎会枚举到len(s)但真正进入递归分支的子段长度被三条合法性剪枝限制为最多 3 位。也就是说虽然循环上界写的是len(s)实际有效分支数由剪枝规则约束在常数 $3$ 以内因此递归层数即 IP 段数固定为 $4$整棵决策树的节点数上界为 $O(3^4)$。这正是该题时间复杂度的精确来源。5. 变体思路逐层插入.的写法仓库中收录的 LCR 087. 复原 IP 地址 是同题的官方变体其解法采用了另一种等价实现不维护path子段数组而是直接在字符串中插入.符号用point_num记录已插入的点数。核心思路如下使用res存储所有有效 IP 地址用point_num表示当前 IP 地址中.符号的个数定义回溯方法从start_index位置开始遍历字符串如果字符串中添加的.符号数量为3则判断当前字符串是否为有效 IP 地址如果为有效 IP 地址则加入到res数组中直接返回然后在[start_index, len(s) - 1]范围循环遍历判断[start_index, i]范围所代表的子串是否合法。如果合法则point_num 1然后在i位置后边增加.符号继续回溯遍历最后point_num - 1进行回退不符合则直接跳出循环最后返回res。完整代码class Solution: res [] def backstrack(self, s: str, start_index: int, point_num: int): if point_num 3: if self.isValid(s, start_index, len(s) - 1): self.res.append(s) return for i in range(start_index, len(s)): if self.isValid(s, start_index, i): point_num 1 self.backstrack(s[:i 1] . s[i 1:], i 2, point_num) point_num - 1 else: break def isValid(self, s: str, start: int, end: int): if start end: return False if s[start] 0 and start ! end: return False num 0 for i in range(start, end 1): if s[i] 9 or s[i] 0: return False num num * 10 ord(s[i]) - ord(0) if num 255: return False return True def restoreIpAddresses(self, s: str) - List[str]: self.res.clear() if len(s) 12: return self.res self.backstrack(s, 0, 0) return self.res两种写法的对比如下维度思路 1path 子段数组版思路 2插入.版状态表示path存放已切出的各段直接修改字符串并插入.段数控制len(path) 4剪枝point_num 3后校验合法段校验枚举时内联三条剪枝规则单独抽取isValid函数结束判定len(path) 4 and index len(s)point_num 3且末段合法特点逻辑集中、结构清晰符合「逐点插入」的直觉便于复用校验函数值得注意的细节思路 2 在restoreIpAddresses入口处增加了if len(s) 12: return self.res的提前返回。这是因为每段最多 3 位、共 4 段长度超过 12 的字符串必然无法构成有效 IP属于入口级剪枝。从源码结构看思路 2 的isValid用逐位累加num num * 10 ord(s[i]) - ord(0)的方式判断是否超过 255比思路 1 直接int(sub)更贴近底层字符处理也顺便完成了数字字符校验。6. 总结与同类题型延伸6.1 核心要点回顾回溯三步走明确选择切出当前段→ 明确终止条件切满 4 段且字符用尽→ 翻译成「选择-递归-撤销」代码前导 0 的判定是本题最容易遗漏的边界条件需要同时覆盖「0 只能单独成段」与「非 0 段不能以 0 开头」两种情况常数级剪枝每段最多 3 位数字将决策树规模限制在 $O(3^4)$这是本题时间复杂度的关键来源入口剪枝长度大于 12 的字符串可以直接返回空结果思路 2 的len(s) 12判断属于可选的额外优化。6.2 在回溯算法学习路径中的位置本题属于典型的「组合型切割」回溯题在一个线性序列上枚举切割点并对每一段施加合法性约束。它与仓库回溯章节中的其他经典题形成完整的练习脉络0046. 全排列排列型回溯顺序敏感逐位选元素0078. 子集子集型回溯每个元素选或不选0022. 括号生成括号合法性约束下的生成型回溯0017. 电话号码的字母组合映射枚举型回溯0039. 组合总和 与 0040. 组合总和 II组合型回溯顺序不敏感、可重复/不可重复选择0079. 单词搜索网格上的深度优先搜索回溯。更多回溯类题目可参考 回溯算法题目分类列表 中「回溯算法题目」一节以及 面试 100 题列表、面试 200 题列表 中对应题号的收录情况。建议在掌握本题后同步练习上述题目进一步体会「选择-递归-撤销」在排列、组合、切割、子集四类问题中的统一框架。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode-Go 题解精讲93. Restore IP Addresses —— 用 DFS 回溯复原所有合法 IP 地址LeetCode Go 题解精讲93. Restore IP Addresses —— 用 DFS 回溯复原所有合法 IP 地址 本文以 LeetCode G示例工程leetcode 0093 Restore IP Addresses回溯与枚举两种解法的完整实现、复杂度分析与常见陷阱leetcode 0093 Restore IP Addresses回溯与枚举两种解法的完整实现、复杂度分析与常见陷阱 本文围绕 LeetCode 0093「示例工程教程GitHub_Trending/leetcode1/leetcode复原IP地址回溯法的合法性判断技巧GitHub_Trending/leetcode1/leetcode复原IP地址回溯法的合法性判断技巧 问题定义与核心挑战 IP地址Internet Pro示例工程教程上一篇Camunda 7 Webapps 深度解析Cockpit / Tasklist / Admin 前端架构与本地开发构建指南下一篇如何高效下载B站视频5分钟掌握跨平台开源工具BilibiliDown创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
0093. 复原 IP 地址（Restore IP Addresses）：回溯算法实战解析
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文基于「算法通关手册」仓库中的 restore-ip-addresses.md 题解文档整理而成结合 回溯算法基础讲解 及仓库内同名变体题解 LCR 087. 复原 IP 地址 进行源码级扩充。你将掌握有效 IP 地址的判定规则、用「选择-递归-撤销」三步走实现回溯的思路、剪枝优化的两种写法以及复杂度分析的严谨推导。1. 题目概述题目编号0093. 复原 IP 地址标签字符串、回溯难度中等1.1 题目链接0093. 复原 IP 地址 - 力扣LeetCode1.2 题目大意描述给定一个只包含数字的字符串s用来表示一个 IP 地址。要求返回所有由s构成的有效 IP 地址这些地址可以通过在s中插入.来形成。不能重新排序或删除s中的任何数字。可以按任何顺序返回答案。说明有效 IP 地址正好由四个整数每个整数由 $0 \sim 255$ 的数构成且不能含有前导 0整数之间用.分割。$1 \le s.length \le 20$。s仅由数字组成。示例示例 1输入s 25525511135 输出[255.255.11.135,255.255.111.35]示例 2输入s 0000 输出[0.0.0.0]关于这道题在仓库中的收录情况该题同时出现在 题解总列表、面试 100 题列表、面试 200 题列表 以及 回溯算法题目分类列表 中是算法面试中字符串与回溯结合的高频考点。力扣官方还提供了等价变体题LCR 087. 复原 IP 地址其题解见 docs/solutions/LCR/0on3uN.md。2. 解题思路回溯算法一个有效 IP 地址由四个整数构成中间用 $3$ 个点隔开。现在给定的是无分隔的整数字符串我们可以通过在整数字符串中间的不同位置插入 $3$ 个点来生成不同的 IP 地址。这个过程可以通过回溯算法来生成。本题与 0078. 子集、0046. 全排列 等题一样本质上是「组合型」回溯在字符串的 $|s|-1$ 个间隔位置中选择 $3$ 个位置插入.把字符串切分成 $4$ 段。由于每段必须是 $0 \sim 255$ 之间的合法整数且不能有前导 0因此候选切割方案非常有限。2.1 回顾回溯算法三步走仓库中 回溯算法基础 一节给出了回溯算法的通用方法论通过深度优先搜索不断尝试所有可能的选择当发现当前路径不满足条件时就回退回溯尝试其他路径最终找到所有可行解。其基本步骤如下明确所有选择画出决策树理清每一步有哪些可选项。每个节点的分支代表一次选择。明确终止条件终止条件通常是递归到某一深度、遍历完所有元素或满足题目要求。到达终止条件时处理当前结果如加入答案集。将决策树和终止条件转化为代码定义回溯函数明确函数意义、传入参数、返回结果等书写回溯函数主体给出约束条件、选择元素、递归搜索、撤销选择部分明确递归终止条件给出递归终止条件以及递归终止时的处理方法。通用模板为def backtrack(参数): if 终止条件: 处理结果 return for 选择 in 可选列表: if 满足约束: 做选择 backtrack(新参数) 撤销选择下面严格按这三步走分析复原 IP 地址问题。2.2 明确所有选择对于当前的剩余子串我们要切割出一个合法的 IP 子段。因为 IP 地址每一段的取值范围是 $0 \sim 255$最多 3 位数字所以当前段的起点只能是index终点i只能取index、index 1、index 2即最多枚举 3 种子段长度。这正是本题回溯分支数量被限制在 $O(3^4)$ 的根本原因——决策树每一层最多 3 个分支整棵树深度最多 4 层。2.3 明确终止条件当遍历到决策树的叶子节点时就终止了即当前路径搜索到末尾时递归终止。具体到本题当存放当前结果的数组path的长度等于 $4$并且剩余字符开始位置为字符串结束位置即len(path) 4 and index len(s)时说明已经切出 4 段且用完了所有字符递归停止将当前结果加入答案如果回溯过程中切割次数大于 4即len(path) 4说明已经超出了 IP 地址应有的段数递归停止直接返回。2.4 将决策树和终止条件翻译成代码1. 定义回溯函数backtracking(index)函数的传入参数是index剩余字符开始位置全局变量是res存放所有符合条件结果的集合数组和path存放当前符合条件的结果。backtracking(index)函数代表的含义是递归从index位置开始从剩下字符中选择当前子段的值。2. 书写回溯函数主体给出选择元素、递归搜索、撤销选择部分从当前正在考虑的字符index到字符串结束为止枚举出所有可作为当前子段值的字符。对于每一个子段值约束条件只能从index位置开始选择并且要符合规则要求数值在 $0 \sim 255$ 之间、无前导 0选择元素将其添加到当前子段数组path中递归搜索在选择该子段值的情况下继续递归从剩下字符中选择下一个子段值撤销选择将该子段值从当前结果数组path中移除。for i in range(index, len(s)): # 枚举可选元素列表 sub s[index: i 1] # 如果当前值不在 0 ~ 255 之间直接跳过 if int(sub) 255: continue # 如果当前值为 0但不是单个 000...直接跳过 if int(sub) 0 and i ! index: continue # 如果当前值大于 0但是以 0 开头0XX...直接跳过 if int(sub) 0 and s[index] 0: continue path.append(sub) # 选择元素 backtracking(i 1) # 递归搜索 path.pop() # 撤销选择3. 明确递归终止条件给出递归终止条件以及递归终止时的处理方法当遍历到决策树的叶子节点时就终止了。也就是存放当前结果的数组path的长度等于 $4$并且剩余字符开始位置为字符串结束位置即len(path) 4 and index len(s)时递归停止如果回溯过程中切割次数大于 4即len(path) 4递归停止直接返回。2.5 三条合法性剪枝规则详解上述代码中的三条continue剪枝是本题的核心缺一不可逐一说明剪枝条件拦截的非法子段示例int(sub) 255数值超出 $0 \sim 255$ 范围256、999int(sub) 0 and i ! index值为 0 但长度大于 1前导 000、000int(sub) 0 and s[index] 0值大于 0 却以 0 开头前导 001、023三条规则共同保证了「不能含有前导 0」的判定数字0只能以单个0的形式出现而01、00这类子段一律拒绝。在时间约束下这三条规则也保证了决策树的每个节点最多只有 3 个合法分支因为长度超过 3 的子段必然 255在枚举到i index 2之后就会被int(sub) 255剪掉。3. 完整代码实现class Solution: def restoreIpAddresses(self, s: str) - List[str]: res [] path [] def backtracking(index): # 如果切割次数大于 4直接返回 if len(path) 4: return # 切割完成将当前结果加入答案结果数组中 if len(path) 4 and index len(s): res.append(..join(path)) return for i in range(index, len(s)): sub s[index: i 1] # 如果当前值不在 0 ~ 255 之间直接跳过 if int(sub) 255: continue # 如果当前值为 0但不是单个 000...直接跳过 if int(sub) 0 and i ! index: continue # 如果当前值大于 0但是以 0 开头0XX...直接跳过 if int(sub) 0 and s[index] 0: continue path.append(sub) backtracking(i 1) path.pop() backtracking(0) return res3.1 代码运行验证对题目给出的示例以及一个扩展用例运行上述实现已在本地 Python 3 环境中实测验证 Solution().restoreIpAddresses(25525511135) [255.255.11.135, 255.255.111.35] Solution().restoreIpAddresses(0000) [0.0.0.0] Solution().restoreIpAddresses(101023) [1.0.10.23, 1.0.102.3, 10.1.0.23, 10.10.2.3, 101.0.2.3]可以看到25525511135恰好得到题面给出的两种答案0000因为前导 0 规则的限制只能切分成0.0.0.0一种方案其余如0.00.0.0均被剪枝101023得到 5 种合法 IP覆盖了多种切割组合验证了回溯对全解空间的穷举能力。3.2 递归执行过程速览以 s 25525511135 为例第 1 层index 0候选子段为2、25、2552552因int 255被剪枝第 2 层例如已选255后从index 3继续候选为2、25、255第 3 层继续从下一个index枚举 3 种子段第 4 层当len(path)达到 4 且index len(s)时将..join(path)写入res并返回每层递归返回后执行path.pop()撤销当前子段恢复现场以尝试下一个分支。由于每层最多 3 个分支、最多 4 层搜索树规模极小无需额外的记忆化或动态规划优化即可通过全部测试用例。4. 复杂度分析时间复杂度$O(3^4 \times |s|)$其中 $|s|$ 是字符串s的长度。由于 IP 地址的每一子段位数不会超过 $3$因此在递归时我们最多只会深入到下一层中的 $3$ 种情况。而 IP 地址由 $4$ 个子段构成所以递归的最大层数为 $4$ 层则递归的时间复杂度为 $O(3^4)$。而每次将有效的 IP 地址添加到答案数组的时间复杂度为 $|s|$所以总的时间复杂度为 $3^4 \times |s|$。空间复杂度$O(|s|)$只记录除了用来存储答案数组之外的空间复杂度。递归栈深度不超过 4 层加上path与字符串切片sub的存储空间开销与字符串长度线性相关。4.1 复杂度分析的严谨性说明从代码结构看for i in range(index, len(s))表面上似乎会枚举到len(s)但真正进入递归分支的子段长度被三条合法性剪枝限制为最多 3 位。也就是说虽然循环上界写的是len(s)实际有效分支数由剪枝规则约束在常数 $3$ 以内因此递归层数即 IP 段数固定为 $4$整棵决策树的节点数上界为 $O(3^4)$。这正是该题时间复杂度的精确来源。5. 变体思路逐层插入.的写法仓库中收录的 LCR 087. 复原 IP 地址 是同题的官方变体其解法采用了另一种等价实现不维护path子段数组而是直接在字符串中插入.符号用point_num记录已插入的点数。核心思路如下使用res存储所有有效 IP 地址用point_num表示当前 IP 地址中.符号的个数定义回溯方法从start_index位置开始遍历字符串如果字符串中添加的.符号数量为3则判断当前字符串是否为有效 IP 地址如果为有效 IP 地址则加入到res数组中直接返回然后在[start_index, len(s) - 1]范围循环遍历判断[start_index, i]范围所代表的子串是否合法。如果合法则point_num 1然后在i位置后边增加.符号继续回溯遍历最后point_num - 1进行回退不符合则直接跳出循环最后返回res。完整代码class Solution: res [] def backstrack(self, s: str, start_index: int, point_num: int): if point_num 3: if self.isValid(s, start_index, len(s) - 1): self.res.append(s) return for i in range(start_index, len(s)): if self.isValid(s, start_index, i): point_num 1 self.backstrack(s[:i 1] . s[i 1:], i 2, point_num) point_num - 1 else: break def isValid(self, s: str, start: int, end: int): if start end: return False if s[start] 0 and start ! end: return False num 0 for i in range(start, end 1): if s[i] 9 or s[i] 0: return False num num * 10 ord(s[i]) - ord(0) if num 255: return False return True def restoreIpAddresses(self, s: str) - List[str]: self.res.clear() if len(s) 12: return self.res self.backstrack(s, 0, 0) return self.res两种写法的对比如下维度思路 1path 子段数组版思路 2插入.版状态表示path存放已切出的各段直接修改字符串并插入.段数控制len(path) 4剪枝point_num 3后校验合法段校验枚举时内联三条剪枝规则单独抽取isValid函数结束判定len(path) 4 and index len(s)point_num 3且末段合法特点逻辑集中、结构清晰符合「逐点插入」的直觉便于复用校验函数值得注意的细节思路 2 在restoreIpAddresses入口处增加了if len(s) 12: return self.res的提前返回。这是因为每段最多 3 位、共 4 段长度超过 12 的字符串必然无法构成有效 IP属于入口级剪枝。从源码结构看思路 2 的isValid用逐位累加num num * 10 ord(s[i]) - ord(0)的方式判断是否超过 255比思路 1 直接int(sub)更贴近底层字符处理也顺便完成了数字字符校验。6. 总结与同类题型延伸6.1 核心要点回顾回溯三步走明确选择切出当前段→ 明确终止条件切满 4 段且字符用尽→ 翻译成「选择-递归-撤销」代码前导 0 的判定是本题最容易遗漏的边界条件需要同时覆盖「0 只能单独成段」与「非 0 段不能以 0 开头」两种情况常数级剪枝每段最多 3 位数字将决策树规模限制在 $O(3^4)$这是本题时间复杂度的关键来源入口剪枝长度大于 12 的字符串可以直接返回空结果思路 2 的len(s) 12判断属于可选的额外优化。6.2 在回溯算法学习路径中的位置本题属于典型的「组合型切割」回溯题在一个线性序列上枚举切割点并对每一段施加合法性约束。它与仓库回溯章节中的其他经典题形成完整的练习脉络0046. 全排列排列型回溯顺序敏感逐位选元素0078. 子集子集型回溯每个元素选或不选0022. 括号生成括号合法性约束下的生成型回溯0017. 电话号码的字母组合映射枚举型回溯0039. 组合总和 与 0040. 组合总和 II组合型回溯顺序不敏感、可重复/不可重复选择0079. 单词搜索网格上的深度优先搜索回溯。更多回溯类题目可参考 回溯算法题目分类列表 中「回溯算法题目」一节以及 面试 100 题列表、面试 200 题列表 中对应题号的收录情况。建议在掌握本题后同步练习上述题目进一步体会「选择-递归-撤销」在排列、组合、切割、子集四类问题中的统一框架。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode-Go 题解精讲93. Restore IP Addresses —— 用 DFS 回溯复原所有合法 IP 地址LeetCode Go 题解精讲93. Restore IP Addresses —— 用 DFS 回溯复原所有合法 IP 地址 本文以 LeetCode G示例工程leetcode 0093 Restore IP Addresses回溯与枚举两种解法的完整实现、复杂度分析与常见陷阱leetcode 0093 Restore IP Addresses回溯与枚举两种解法的完整实现、复杂度分析与常见陷阱 本文围绕 LeetCode 0093「示例工程教程GitHub_Trending/leetcode1/leetcode复原IP地址回溯法的合法性判断技巧GitHub_Trending/leetcode1/leetcode复原IP地址回溯法的合法性判断技巧 问题定义与核心挑战 IP地址Internet Pro示例工程教程上一篇Camunda 7 Webapps 深度解析Cockpit / Tasklist / Admin 前端架构与本地开发构建指南下一篇如何高效下载B站视频5分钟掌握跨平台开源工具BilibiliDown创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
