2026/9/13 16:58:39
FEATURED · 精选文章 
LeetCode-Go 题解 0093用 DFS 回溯与可复用段切片复原 IP 地址【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术文章基于 LeetCode-Go 仓库中第 93 题 Restore IP Addresses 的题解文档完整给出“给定纯数字字符串枚举所有合法 IP 地址”的 DFS 回溯解法包括 IP 合法性两条核心规则、完整 Go 代码、逐函数实现细节以及仓库内配套测试用例的验证方式。读完你能理解这套“共享切片 原位撤销”的回溯写法如何避免每层递归都复制状态并能在本仓库中直接运行测试复现结果。题目与 IP 合法性规则题目原文继承自 英文题解文档 与 中文题解文档Given a string containing only digits, restore it by returning all possible valid IP address combinations.给定一个只包含数字的字符串复原它并返回所有可能的 IP 地址格式。示例Input: 25525511135 Output: [255.255.11.135, 255.255.111.35]复原为合法 IPv4 地址时必须满足题解文档“解题思路”一节强调的两条规则每个地址由恰好 4 段组成每段取 13 个数字且以 0 开头的多位数非法如 01 不合法0 本身合法每段的数值不得超过 255。由于每段最多取 3 位合法 IP 的总长度上限为 12 个字符因此输入超过 12 位时答案必为空集这也从侧面限定了搜索树的规模上限。解题思路DFS 深搜题解文档给出的方法就是 DFS深度优先搜索从左到右扫描字符串每个位置做出二选一决策——把当前数字并进上一段凑 2 位数或者从当前数字开始开启新的一段凑 1 位数。当扫描到字符串末尾且恰好凑满 4 段时记录一个完整答案。回溯过程中需要维护两条合法性剪枝以 0 开头的数字和超过 255 的数字都为非法。完整 Go 解法以下是仓库中 源码文件 的完整实现与题解文档中的代码一致package leetcode import ( strconv ) func restoreIPAddresses(s string) []string { if s { return []string{} } res, ip : []string{}, []int{} dfs(s, 0, ip, res) return res } func dfs(s string, index int, ip []int, res *[]string) { if index len(s) { if len(ip) 4 { *res append(*res, getString(ip)) } return } if index 0 { num, _ : strconv.Atoi(string(s[0])) ip append(ip, num) dfs(s, index1, ip, res) } else { num, _ : strconv.Atoi(string(s[index])) next : ip[len(ip)-1]*10 num if next 255 ip[len(ip)-1] ! 0 { ip[len(ip)-1] next dfs(s, index1, ip, res) ip[len(ip)-1] / 10 } if len(ip) 4 { ip append(ip, num) dfs(s, index1, ip, res) ip ip[:len(ip)-1] } } } func getString(ip []int) string { res : strconv.Itoa(ip[0]) for i : 1; i len(ip); i { res . strconv.Itoa(ip[i]) } return res }三个函数分工明确restoreIPAddresses入口函数。空串直接返回非 nil 的空切片[]string{}对应测试用例否则初始化res收集结果与ip当前正在构造的段序列从下标 0 启动 DFS。dfs核心递归参数为字符串、当前扫描下标index、可变段序列ip、结果指针res。getString将 4 个 int 段用.拼接成字符串只在凑满 4 段时才会被调用因此直接下标访问ip[0..3]是安全的。实现细节剖析终止条件字符串耗尽且恰好 4 段if index len(s) { if len(ip) 4 { *res append(*res, getString(ip)) } return }扫描到末尾index len(s)即到达叶子节点。此时仅当len(ip) 4才记录答案——这同时隐式处理了两类失败情形段数不足 4还有数字没分段和段数已满但后面还有剩余字符在开新段分支中被len(ip) 4挡住不会走到这里。起点分支第一段只能“新开”if index 0 { num, _ : strconv.Atoi(string(s[0])) ip append(ip, num) dfs(s, index1, ip, res) }第一个字符没有“上一段”可扩展所以只能作为第一段的个位直接入列后进入递归。注意这里没有对num做 255 剪枝——个位数字最大为 9天然合法strconv.Atoi的 error 被有意忽略_因为题目保证输入只含数字。两条分支扩展末段 vs 新开一段进入else分支时num是当前字符s[index]的数值。第一条分支尝试把num追加到末段的个位next : ip[len(ip)-1]*10 num if next 255 ip[len(ip)-1] ! 0 { ip[len(ip)-1] next dfs(s, index1, ip, res) ip[len(ip)-1] / 10 }next 255对应“超过 255 非法”规则例如末段已是 25再来任何数字next 落在 250~259都会被剪掉ip[len(ip)-1] ! 0对应“以 0 开头非法”规则。末段为 0 时再挂一个数字拼出来就是 01~09 这类前导零数字直接剪枝剪枝之外还有一个隐含约束末段本身必须是 1 位数10扩展后才是 2 位数末段已经是 2 位数如 42时next 420 num 255同样被 255 条件挡下。因此每段长度天然被限制在 1~3 位。第二条分支是从当前数字新开一段if len(ip) 4 { ip append(ip, num) dfs(s, index1, ip, res) ip ip[:len(ip)-1] }len(ip) 4保证最多 4 段递归返回后通过切片截断ip ip[:len(ip)-1]撤销本次入列。共享切片与“除以 10”的原位回溯这套实现最值得注意的工程细节是整棵搜索树只使用一个ip切片通过“入列/截断”和“改写末段/回改末段”完成状态保存与恢复而不是每层递归拷贝一份段序列。尤其是扩展末段的撤销操作写得相当巧妙——恢复用的不是栈里存的旧值而是ip[len(ip)-1] / 10由于扩展时的取值是next last*10 numnum ∈ 0..9整除 10 恰好还原出last。这行代码的正确性依赖于next一定满足next/10 last这一整数除法性质阅读该源码时值得留意。从源码结构看该实现没有额外做“剩余字符数必须够分给剩余段数”的可行性剪枝例如新开一段后检查len(s)-index-1是否至少等于还需的段数、至多等于 3 倍段数。由于len(ip) 4与叶子处的len(ip) 4兜底结果依然正确只是会多探索少量死路分支对长度 ≤ 12 的输入而言开销可忽略属于可选项而非缺陷。用仓库测试用例验证与题解同目录的 测试文件 定义了Test_Problem93覆盖 4 组用例正好把上述剪枝逻辑的关键路径都打到了输入期望输出覆盖点25525511135[255.255.11.135, 255.255.111.35]文档示例末段扩展与 255 边界255 合法2552… 被剪0000[0.0.0.0]前导零剪枝末段为 0 时禁止扩展只能 4 段各 1 位010010[0.10.0.10, 0.100.1.0]首段 0 合法、后续 01… 形态被剪验证两条分支的组合枚举[]空串入口分支返回非 nil 空切片测试运行时会通过fmt.Printf打印每组的【input】/【output】对照。在仓库根目录执行go test -v ./leetcode/0093.Restore-IP-Addresses/即可看到输出仓库根目录的 gotest.sh 则给出全量运行方式go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...用于生成该仓库宣传的 100% 覆盖率报告。复杂度小结设字符串长度为 n合法输入 n ≤ 12时间复杂度每个位置最多产生两条递归分支扩展末段 / 新开一段最坏 O(2^n)受 255、前导零、4 段上限三重剪枝实际分支数远小于上界n 又被 12 锁死规模极小。空间复杂度递归深度 n共享的ip切片至多 4 个元素除输出res外为 O(n)。相关文件索引英文题解文档本篇主体中文题解文档解题源码单元测试题目说明全量测试脚本本文所有代码与测试输出均可在只读克隆本仓库后按上述命令直接复现无需任何额外依赖。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解 0093：用 DFS 回溯与可复用段切片复原 IP 地址
LeetCode-Go 题解 0093用 DFS 回溯与可复用段切片复原 IP 地址【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术文章基于 LeetCode-Go 仓库中第 93 题 Restore IP Addresses 的题解文档完整给出“给定纯数字字符串枚举所有合法 IP 地址”的 DFS 回溯解法包括 IP 合法性两条核心规则、完整 Go 代码、逐函数实现细节以及仓库内配套测试用例的验证方式。读完你能理解这套“共享切片 原位撤销”的回溯写法如何避免每层递归都复制状态并能在本仓库中直接运行测试复现结果。题目与 IP 合法性规则题目原文继承自 英文题解文档 与 中文题解文档Given a string containing only digits, restore it by returning all possible valid IP address combinations.给定一个只包含数字的字符串复原它并返回所有可能的 IP 地址格式。示例Input: 25525511135 Output: [255.255.11.135, 255.255.111.35]复原为合法 IPv4 地址时必须满足题解文档“解题思路”一节强调的两条规则每个地址由恰好 4 段组成每段取 13 个数字且以 0 开头的多位数非法如 01 不合法0 本身合法每段的数值不得超过 255。由于每段最多取 3 位合法 IP 的总长度上限为 12 个字符因此输入超过 12 位时答案必为空集这也从侧面限定了搜索树的规模上限。解题思路DFS 深搜题解文档给出的方法就是 DFS深度优先搜索从左到右扫描字符串每个位置做出二选一决策——把当前数字并进上一段凑 2 位数或者从当前数字开始开启新的一段凑 1 位数。当扫描到字符串末尾且恰好凑满 4 段时记录一个完整答案。回溯过程中需要维护两条合法性剪枝以 0 开头的数字和超过 255 的数字都为非法。完整 Go 解法以下是仓库中 源码文件 的完整实现与题解文档中的代码一致package leetcode import ( strconv ) func restoreIPAddresses(s string) []string { if s { return []string{} } res, ip : []string{}, []int{} dfs(s, 0, ip, res) return res } func dfs(s string, index int, ip []int, res *[]string) { if index len(s) { if len(ip) 4 { *res append(*res, getString(ip)) } return } if index 0 { num, _ : strconv.Atoi(string(s[0])) ip append(ip, num) dfs(s, index1, ip, res) } else { num, _ : strconv.Atoi(string(s[index])) next : ip[len(ip)-1]*10 num if next 255 ip[len(ip)-1] ! 0 { ip[len(ip)-1] next dfs(s, index1, ip, res) ip[len(ip)-1] / 10 } if len(ip) 4 { ip append(ip, num) dfs(s, index1, ip, res) ip ip[:len(ip)-1] } } } func getString(ip []int) string { res : strconv.Itoa(ip[0]) for i : 1; i len(ip); i { res . strconv.Itoa(ip[i]) } return res }三个函数分工明确restoreIPAddresses入口函数。空串直接返回非 nil 的空切片[]string{}对应测试用例否则初始化res收集结果与ip当前正在构造的段序列从下标 0 启动 DFS。dfs核心递归参数为字符串、当前扫描下标index、可变段序列ip、结果指针res。getString将 4 个 int 段用.拼接成字符串只在凑满 4 段时才会被调用因此直接下标访问ip[0..3]是安全的。实现细节剖析终止条件字符串耗尽且恰好 4 段if index len(s) { if len(ip) 4 { *res append(*res, getString(ip)) } return }扫描到末尾index len(s)即到达叶子节点。此时仅当len(ip) 4才记录答案——这同时隐式处理了两类失败情形段数不足 4还有数字没分段和段数已满但后面还有剩余字符在开新段分支中被len(ip) 4挡住不会走到这里。起点分支第一段只能“新开”if index 0 { num, _ : strconv.Atoi(string(s[0])) ip append(ip, num) dfs(s, index1, ip, res) }第一个字符没有“上一段”可扩展所以只能作为第一段的个位直接入列后进入递归。注意这里没有对num做 255 剪枝——个位数字最大为 9天然合法strconv.Atoi的 error 被有意忽略_因为题目保证输入只含数字。两条分支扩展末段 vs 新开一段进入else分支时num是当前字符s[index]的数值。第一条分支尝试把num追加到末段的个位next : ip[len(ip)-1]*10 num if next 255 ip[len(ip)-1] ! 0 { ip[len(ip)-1] next dfs(s, index1, ip, res) ip[len(ip)-1] / 10 }next 255对应“超过 255 非法”规则例如末段已是 25再来任何数字next 落在 250~259都会被剪掉ip[len(ip)-1] ! 0对应“以 0 开头非法”规则。末段为 0 时再挂一个数字拼出来就是 01~09 这类前导零数字直接剪枝剪枝之外还有一个隐含约束末段本身必须是 1 位数10扩展后才是 2 位数末段已经是 2 位数如 42时next 420 num 255同样被 255 条件挡下。因此每段长度天然被限制在 1~3 位。第二条分支是从当前数字新开一段if len(ip) 4 { ip append(ip, num) dfs(s, index1, ip, res) ip ip[:len(ip)-1] }len(ip) 4保证最多 4 段递归返回后通过切片截断ip ip[:len(ip)-1]撤销本次入列。共享切片与“除以 10”的原位回溯这套实现最值得注意的工程细节是整棵搜索树只使用一个ip切片通过“入列/截断”和“改写末段/回改末段”完成状态保存与恢复而不是每层递归拷贝一份段序列。尤其是扩展末段的撤销操作写得相当巧妙——恢复用的不是栈里存的旧值而是ip[len(ip)-1] / 10由于扩展时的取值是next last*10 numnum ∈ 0..9整除 10 恰好还原出last。这行代码的正确性依赖于next一定满足next/10 last这一整数除法性质阅读该源码时值得留意。从源码结构看该实现没有额外做“剩余字符数必须够分给剩余段数”的可行性剪枝例如新开一段后检查len(s)-index-1是否至少等于还需的段数、至多等于 3 倍段数。由于len(ip) 4与叶子处的len(ip) 4兜底结果依然正确只是会多探索少量死路分支对长度 ≤ 12 的输入而言开销可忽略属于可选项而非缺陷。用仓库测试用例验证与题解同目录的 测试文件 定义了Test_Problem93覆盖 4 组用例正好把上述剪枝逻辑的关键路径都打到了输入期望输出覆盖点25525511135[255.255.11.135, 255.255.111.35]文档示例末段扩展与 255 边界255 合法2552… 被剪0000[0.0.0.0]前导零剪枝末段为 0 时禁止扩展只能 4 段各 1 位010010[0.10.0.10, 0.100.1.0]首段 0 合法、后续 01… 形态被剪验证两条分支的组合枚举[]空串入口分支返回非 nil 空切片测试运行时会通过fmt.Printf打印每组的【input】/【output】对照。在仓库根目录执行go test -v ./leetcode/0093.Restore-IP-Addresses/即可看到输出仓库根目录的 gotest.sh 则给出全量运行方式go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...用于生成该仓库宣传的 100% 覆盖率报告。复杂度小结设字符串长度为 n合法输入 n ≤ 12时间复杂度每个位置最多产生两条递归分支扩展末段 / 新开一段最坏 O(2^n)受 255、前导零、4 段上限三重剪枝实际分支数远小于上界n 又被 12 锁死规模极小。空间复杂度递归深度 n共享的ip切片至多 4 个元素除输出res外为 O(n)。相关文件索引英文题解文档本篇主体中文题解文档解题源码单元测试题目说明全量测试脚本本文所有代码与测试输出均可在只读克隆本仓库后按上述命令直接复现无需任何额外依赖。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
