题目描述
思路解析动画文字版
记住节奏：取段 → 合法就深入、非法就剪 → 满 4 段且字符用完才收。下面逐帧看它怎么跑。
从下标 0 起取 1 位 = "2"。值 2 ≤255、无前导 0，合法 → 当作第 1 段取进 path，接着从下标 1 切下一段。
从下标 1 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 2 切下一段。
从下标 2 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 3 切下一段。
从下标 3 起取 1 位 = "2"。值 2 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 4 切下一段。
从下标 3 起取 2 位 = "25"。值 25 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 5 切下一段。
从下标 3 起取 3 位 = "255"。值 255 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
从下标 2 起取 2 位 = "52"。值 52 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 4 切下一段。
从下标 4 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 5 切下一段。
从下标 4 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
试从下标 4 取 3 位 = "551"：值 551 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
试从下标 2 取 3 位 = "525"：值 525 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
从下标 1 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 3 切下一段。
从下标 3 起取 1 位 = "2"。值 2 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 4 切下一段。
从下标 4 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 5 切下一段。
从下标 4 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
试从下标 4 取 3 位 = "551"：值 551 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
从下标 3 起取 2 位 = "25"。值 25 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 5 切下一段。
从下标 5 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
从下标 5 起取 2 位 = "51"。值 51 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
试从下标 5 取 3 位 = "511"：值 511 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
从下标 3 起取 3 位 = "255"。值 255 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 6 切下一段。
从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
试从下标 1 取 3 位 = "552"：值 552 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
从下标 0 起取 2 位 = "25"。值 25 ≤255、无前导 0，合法 → 当作第 1 段取进 path，接着从下标 2 切下一段。
从下标 2 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 3 切下一段。
从下标 3 起取 1 位 = "2"。值 2 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 4 切下一段。
从下标 4 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 5 切下一段。
从下标 4 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
试从下标 4 取 3 位 = "551"：值 551 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
从下标 3 起取 2 位 = "25"。值 25 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 5 切下一段。
从下标 5 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
从下标 5 起取 2 位 = "51"。值 51 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
试从下标 5 取 3 位 = "511"：值 511 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
从下标 3 起取 3 位 = "255"。值 255 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 6 切下一段。
从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
从下标 2 起取 2 位 = "52"。值 52 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 4 切下一段。
从下标 4 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 5 切下一段。
从下标 5 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
从下标 5 起取 2 位 = "51"。值 51 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
试从下标 5 取 3 位 = "511"：值 511 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
从下标 4 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 6 切下一段。
从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
试从下标 4 取 3 位 = "551"：值 551 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
试从下标 2 取 3 位 = "525"：值 525 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
从下标 0 起取 3 位 = "255"。值 255 ≤255、无前导 0，合法 → 当作第 1 段取进 path，接着从下标 3 切下一段。
从下标 3 起取 1 位 = "2"。值 2 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 4 切下一段。
从下标 4 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 5 切下一段。
从下标 5 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
从下标 5 起取 2 位 = "51"。值 51 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
试从下标 5 取 3 位 = "511"：值 511 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
从下标 4 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 6 切下一段。
从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
试从下标 4 取 3 位 = "551"：值 551 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
从下标 3 起取 2 位 = "25"。值 25 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 5 切下一段。
从下标 5 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 6 切下一段。
从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
从下标 5 起取 2 位 = "51"。值 51 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 7 切下一段。
从下标 7 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
从下标 7 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
从下标 7 起取 3 位 = "113"。值 113 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 10 切下一段。
试从下标 5 取 3 位 = "511"：值 511 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
从下标 3 起取 3 位 = "255"。值 255 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 6 切下一段。
从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 7 切下一段。
从下标 7 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
从下标 7 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
从下标 7 起取 3 位 = "113"。值 113 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 10 切下一段。
从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 8 切下一段。
从下标 8 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
从下标 8 起取 2 位 = "13"。值 13 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 10 切下一段。
从下标 8 起取 3 位 = "135"。值 135 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 11 切下一段。
已取满 4 段 "255"、"255"、"11"、"135"，且字符正好用完 → 拼成合法 IP 255.255.11.135，收进结果（第 1 个）。
这一支走到底，撤掉刚取的段 "135"（path 弹出），回到 [255, 255, 11]，回退去试同一位置取更长 / 别的切法。
这一支走到底，撤掉刚取的段 "11"（path 弹出），回到 [255, 255]，回退去试同一位置取更长 / 别的切法。
从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 9 切下一段。
从下标 9 起取 1 位 = "3"。值 3 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 10 切下一段。
从下标 9 起取 2 位 = "35"。值 35 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 11 切下一段。
已取满 4 段 "255"、"255"、"111"、"35"，且字符正好用完 → 拼成合法 IP 255.255.111.35，收进结果（第 2 个）。
这一支走到底，撤掉刚取的段 "35"（path 弹出），回到 [255, 255, 111]，回退去试同一位置取更长 / 别的切法。
这一支走到底，撤掉刚取的段 "111"（path 弹出），回到 [255, 255]，回退去试同一位置取更长 / 别的切法。
这一支走到底，撤掉刚取的段 "255"（path 弹出），回到 [255]，回退去试同一位置取更长 / 别的切法。
这一支走到底，撤掉刚取的段 "255"（path 弹出），回到 [ ]，回退去试同一位置取更长 / 别的切法。
边界看「全 0」「多解」「无解」三种：段必须 1~3 位、值 ≤255、字符全用完，缺一不可。
两个高频追问：剪枝的价值 + 「插点」枚举的等价视角。
参考代码
def restoreIpAddresses(s): res, path = [], [] def ok(seg): if not (1 <= len(seg) <= 3): return False if len(seg) > 1 and seg[0] == "0": return False # 前导 0 return int(seg) <= 255 def bt(start): if len(path) == 4: if start == len(s): res.append(".".join(path)) return for L in range(1, 4): # 取 1~3 位 if start + L > len(s): break seg = s[start:start+L] if not ok(seg): continue # 非法剪枝 path.append(seg) # 取这一段 bt(start + L) path.pop() # 回溯撤销 bt(0) return res复杂度
- 时间：O(1)，每段最多试 3 种长度、共 4 段，3⁴=81 种切法封顶，与串长无关（串长 ≤12）
- 空间：O(1)，递归深度恒 ≤4（4 段），path 最多 4 段
易错点
面试追问把动画讲成自己的话
追问为什么剪枝很重要，不剪会怎样？
追问怎么改成「插点」视角的写法？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
分割回文串
LeetCode 131 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题