LeetCode 93中等回溯 · 分段
复原 IP 地址 图解题解
这道题到底在问什么
s 只含数字，插 3 个点切成 4 段，每段须是合法 IPv4 字段；返回所有合法 IP，顺序随意。
- 输入
- s="25525511135"
- 输出
- ["255.255.11.135","255.255.111.35"]
最优解：一步一步想明白
- 3记住节奏：取段 → 合法就深入、非法就剪 → 满 4 段且字符用完才收。下面逐帧看它怎么跑。
- 4从下标 0 起取 1 位 = "2"。值 2 ≤255、无前导 0，合法 → 当作第 1 段取进 path，接着从下标 1 切下一段。
- 5从下标 1 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 2 切下一段。
- 6从下标 2 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 3 切下一段。
- 7从下标 3 起取 1 位 = "2"。值 2 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 4 切下一段。
- 8从下标 3 起取 2 位 = "25"。值 25 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 5 切下一段。
- 9从下标 3 起取 3 位 = "255"。值 255 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
- 10从下标 2 起取 2 位 = "52"。值 52 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 4 切下一段。
- 11从下标 4 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 5 切下一段。
- 12从下标 4 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
- 13试从下标 4 取 3 位 = "551"：值 551 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 14试从下标 2 取 3 位 = "525"：值 525 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 15从下标 1 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 3 切下一段。
- 16从下标 3 起取 1 位 = "2"。值 2 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 4 切下一段。
- 17从下标 4 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 5 切下一段。
- 18从下标 4 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
- 19试从下标 4 取 3 位 = "551"：值 551 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 20从下标 3 起取 2 位 = "25"。值 25 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 5 切下一段。
- 21从下标 5 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
- 22从下标 5 起取 2 位 = "51"。值 51 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
- 23试从下标 5 取 3 位 = "511"：值 511 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 24从下标 3 起取 3 位 = "255"。值 255 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 6 切下一段。
- 25从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
- 26从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
- 27从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
- 28试从下标 1 取 3 位 = "552"：值 552 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 29从下标 0 起取 2 位 = "25"。值 25 ≤255、无前导 0，合法 → 当作第 1 段取进 path，接着从下标 2 切下一段。
- 30从下标 2 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 3 切下一段。
- 31从下标 3 起取 1 位 = "2"。值 2 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 4 切下一段。
- 32从下标 4 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 5 切下一段。
- 33从下标 4 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
- 34试从下标 4 取 3 位 = "551"：值 551 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 35从下标 3 起取 2 位 = "25"。值 25 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 5 切下一段。
- 36从下标 5 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
- 37从下标 5 起取 2 位 = "51"。值 51 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
- 38试从下标 5 取 3 位 = "511"：值 511 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 39从下标 3 起取 3 位 = "255"。值 255 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 6 切下一段。
- 40从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
- 41从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
- 42从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
- 43从下标 2 起取 2 位 = "52"。值 52 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 4 切下一段。
- 44从下标 4 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 5 切下一段。
- 45从下标 5 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
- 46从下标 5 起取 2 位 = "51"。值 51 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
- 47试从下标 5 取 3 位 = "511"：值 511 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 48从下标 4 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 6 切下一段。
- 49从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
- 50从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
- 51从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
- 52试从下标 4 取 3 位 = "551"：值 551 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 53试从下标 2 取 3 位 = "525"：值 525 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 54从下标 0 起取 3 位 = "255"。值 255 ≤255、无前导 0，合法 → 当作第 1 段取进 path，接着从下标 3 切下一段。
- 55从下标 3 起取 1 位 = "2"。值 2 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 4 切下一段。
- 56从下标 4 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 5 切下一段。
- 57从下标 5 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 6 切下一段。
- 58从下标 5 起取 2 位 = "51"。值 51 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
- 59试从下标 5 取 3 位 = "511"：值 511 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 60从下标 4 起取 2 位 = "55"。值 55 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 6 切下一段。
- 61从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
- 62从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
- 63从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
- 64试从下标 4 取 3 位 = "551"：值 551 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 65从下标 3 起取 2 位 = "25"。值 25 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 5 切下一段。
- 66从下标 5 起取 1 位 = "5"。值 5 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 6 切下一段。
- 67从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 7 切下一段。
- 68从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
- 69从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
- 70从下标 5 起取 2 位 = "51"。值 51 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 7 切下一段。
- 71从下标 7 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
- 72从下标 7 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
- 73从下标 7 起取 3 位 = "113"。值 113 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 10 切下一段。
- 74试从下标 5 取 3 位 = "511"：值 511 > 255，超出字段范围，非法 → 画 ✗ 剪掉，不深入这一支。
- 75从下标 3 起取 3 位 = "255"。值 255 ≤255、无前导 0，合法 → 当作第 2 段取进 path，接着从下标 6 切下一段。
- 76从下标 6 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 7 切下一段。
- 77从下标 7 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 8 切下一段。
- 78从下标 7 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
- 79从下标 7 起取 3 位 = "113"。值 113 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 10 切下一段。
- 80从下标 6 起取 2 位 = "11"。值 11 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 8 切下一段。
- 81从下标 8 起取 1 位 = "1"。值 1 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 9 切下一段。
- 82从下标 8 起取 2 位 = "13"。值 13 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 10 切下一段。
- 83从下标 8 起取 3 位 = "135"。值 135 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 11 切下一段。
- 84已取满 4 段 "255"、"255"、"11"、"135"，且字符正好用完 → 拼成合法 IP 255.255.11.135，收进结果（第 1 个）。
- 85这一支走到底，撤掉刚取的段 "135"（path 弹出），回到 [255, 255, 11]，回退去试同一位置取更长 / 别的切法。
- 86这一支走到底，撤掉刚取的段 "11"（path 弹出），回到 [255, 255]，回退去试同一位置取更长 / 别的切法。
- 87从下标 6 起取 3 位 = "111"。值 111 ≤255、无前导 0，合法 → 当作第 3 段取进 path，接着从下标 9 切下一段。
- 88从下标 9 起取 1 位 = "3"。值 3 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 10 切下一段。
- 89从下标 9 起取 2 位 = "35"。值 35 ≤255、无前导 0，合法 → 当作第 4 段取进 path，接着从下标 11 切下一段。
- 90已取满 4 段 "255"、"255"、"111"、"35"，且字符正好用完 → 拼成合法 IP 255.255.111.35，收进结果（第 2 个）。
- 91这一支走到底，撤掉刚取的段 "35"（path 弹出），回到 [255, 255, 111]，回退去试同一位置取更长 / 别的切法。
- 92这一支走到底，撤掉刚取的段 "111"（path 弹出），回到 [255, 255]，回退去试同一位置取更长 / 别的切法。
- 93这一支走到底，撤掉刚取的段 "255"（path 弹出），回到 [255]，回退去试同一位置取更长 / 别的切法。
- 94这一支走到底，撤掉刚取的段 "255"（path 弹出），回到 [ ]，回退去试同一位置取更长 / 别的切法。
⚠️ 容易写错的地方
✗ 错：把 "01" / "00" 当合法
✓ 对：len>1 且首字符为 0 即剪
IPv4 字段不允许前导 0，但单个 "0" 合法，判断要带「长度>1」条件
✗ 错：只看够不够 4 段就收
✓ 对：还要 start == len(s)
取满 4 段但字符没用完，剩下的字符没人要，不是合法 IP，必须刚好用光
✗ 错：段值忘了和 255 比
✓ 对：int(seg) <= 255
"256"/"999" 长度合法但超范围，必须比值；注意 0~255 含 0
完整代码（Python / C++ / Java）
Python
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 resC++
vector<string> restoreIpAddresses(string s){
vector<string> res; vector<string> path;
auto ok = [](const string& seg){
if(seg.empty() || seg.size() > 3) return false;
if(seg.size() > 1 && seg[0] == '0') return false; // 前导 0
return stoi(seg) <= 255;
};
function<void(int)> bt = [&](int start){
if(path.size() == 4){
if(start == (int)s.size()){
string ip = path[0];
for(int k = 1; k < 4; ++k) ip += "." + path[k];
res.push_back(ip);
}
return;
}
for(int L = 1; L <= 3 && start + L <= (int)s.size(); ++L){
string seg = s.substr(start, L);
if(!ok(seg)) continue; // 非法剪枝
path.push_back(seg); // 取段
bt(start + L);
path.pop_back(); // 回溯
}
};
bt(0); return res;
}Java
public List<String> restoreIpAddresses(String s){
List<String> res = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), res);
return res;
}
private boolean ok(String seg){
if(seg.length() < 1 || seg.length() > 3) return false;
if(seg.length() > 1 && seg.charAt(0) == '0') return false; // 前导 0
return Integer.parseInt(seg) <= 255;
}
private void backtrack(String s, int start, List<String> path, List<String> res){
if(path.size() == 4){
if(start == s.length()) res.add(String.join(".", path));
return;
}
for(int L = 1; L <= 3 && start + L <= s.length(); L++){
String seg = s.substring(start, start + L);
if(!ok(seg)) continue; // 非法剪枝
path.add(seg); // 取段
backtrack(s, start + L, path, res);
path.remove(path.size() - 1); // 回溯撤销
}
}复杂度
时间
O(1)
每段最多试 3 种长度、共 4 段，3⁴=81 种切法封顶，与串长无关（串长 ≤12）
空间
O(1)
递归深度恒 ≤4（4 段），path 最多 4 段
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 复原 IP 地址 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么剪枝很重要，不剪会怎样？+
不剪也能跑（4 段、3⁴ 种切法本就是常数），但及早判 >255 / 前导 0 / 越界能砍掉大量无效分支；面试里要能说出「合法性检查放在进入分支前，避免深入死路」。
怎么改成「插点」视角的写法？+
等价地枚举 3 个点的位置：在 4 个间隙里选 3 个切点，对每种切法验 4 段是否都合法。回溯是「逐段取长度」，本质相同，但回溯能自然剪枝、效率更好。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 复原 IP 地址 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。