京公网安备11010502063487号给定一个只含数字的字符串，通过插入三个点把它切成四段，使每一段都是合法的 IP 地址段：数值在 0 到 255 之间，并且不能有前导 0（0 本身合法，00、01 不合法）。返回所有可能的合法 IP 地址。这是回溯的经典应用：依次切四段，每段试 1 到 3 个字符，检查合法性后递归。这道题的特点是搜索空间非常小（每段最多三种切法，一共 3⁴ = 81 种），所以重点不在效率而在合法性检查。本文用真实数据展示漏掉前导 0 检查会多出多少非法地址，给出五种语言的实现，并把切分过程和两种剪枝做成分步演示。
完整题目见官方页面（链接在文末）。结果的顺序不作要求，按集合比较。基准解是三层循环枚举三个切点，再对四段逐一检查，与递归回溯是两种独立的写法。一共 16 组用例，覆盖：官方三个示例、字符串太短或太长（无法切成四段）、超过 255、前导 0、长度恰好 12 的 255255255255：
输入 ["25525511135"] 输出 ["255.255.11.135","255.255.111.35"] 输入 ["0000"] 输出 ["0.0.0.0"] 输入 ["101023"] 输出 ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] 输入 ["1111"] 输出 ["1.1.1.1"] 输入 ["255255255255"] 输出 ["255.255.255.255"] 输入 ["256256256256"] 输出 []
只检查数值不超过 255 是不够的："010" 转成数值是 10，看起来合法，但它有前导 0，不是合法的 IP 段。合法的段只有 "0" 本身，或者以 1 到 9 开头。下面是漏掉前导 0 检查的写法与 solve 的真实结果：
# 没有「不能有前导 0」检查的写法 '25525511135': 该写法 -> ['255.255.11.135', '255.255.111.35'] solve -> ['255.255.11.135', '255.255.111.35'] '0000': 该写法 -> ['0.0.0.0'] solve -> ['0.0.0.0'] '101023': 该写法 -> ['1.0.1.023', '1.0.10.23', '1.0.102.3', '1.01.0.23', '1.01.02.3', '1.010.2.3', '10.1.0.23', '10.1.02.3', '10.10.2.3', '101.0.2.3'] solve -> ['1.0.10.23', '1.0.102.3', '10.1.0.23', '10.10.2.3', '101.0.2.3'] '010010': 该写法 -> ['0.1.0.010', '0.1.00.10', '0.1.001.0', '0.10.0.10', '0.10.01.0', '0.100.1.0', '01.0.0.10', '01.0.01.0', '01.00.1.0', '010.0.1.0'] solve -> ['0.10.0.10', '0.100.1.0'] '00000': 该写法 -> ['0.0.0.00', '0.0.00.0', '0.00.0.0', '00.0.0.0'] solve -> [] 随机 20000 组：该写法出错的有 8760 组（43.8%）
"101023" 应该只有 5 个合法地址，漏检的写法给出 10 个（多出 1.0.1.023、1.01.0.23 这种带前导 0 的非法地址）；"010010" 应该只有 2 个（0.10.0.10 和 0.100.1.0），错误写法给出 10 个；"00000" 应该没有合法地址（五个 0 无法切成四段而每段都是单独的 0，要么某段有 00），错误写法给出 4 个。"25525511135" 和 "0000" 里前导 0 没有影响，两种写法一致。在随机的 20000 组数据里（字符取自 0、1、2、5），错误写法出错的有 8760 组，占 43.8%。
dfs(start)：left = 4 - len(parts) 是还要切几段。left 为 0 时，如果字符串刚好用完（start == len(s)），就把四段用 . 连接后收集；否则失败。剪枝：剩下的字符数 remain 必须在 [left, 3 * left] 之间（每段 1 到 3 个字符），否则直接返回。然后依次尝试这一段的长度 1、2、3：取出这一段 seg，如果它有前导 0（长度大于 1 且以 0 开头）或者数值大于 255，就跳过；否则加入 parts，递归，撤销。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(s): res, parts = [], [] def dfs(start): left = 4 - len(parts) # 还需要切几段 if left == 0: if start == len(s): # 4 段刚好用完整个字符串 res.append(".".join(parts)) return remain = len(s) - start if remain < left or remain > left * 3: # 剪枝：剩下的字符数必须在 [left, 3*left] 之间 return for length in (1, 2, 3): if start + length > len(s): break seg = s[start:start + length] if (len(seg) > 1 and seg[0] == "0") or int(seg) > 255: # 不能有前导 0（"0" 本身可以），数值不超过 255 continue parts.append(seg) dfs(start + length) parts.pop() dfs(0) return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON ["25525511135"] → ["255.255.11.135","255.255.111.35"] ["0000"] → ["0.0.0.0"] ["101023"] → ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] ["1111"] → ["1.1.1.1"] ["255255255255"] → ["255.255.255.255"] ["256256256256"] → []
Java · 解法代码class Solution { public List<String> restoreIpAddresses(String s) { List<String> res = new ArrayList<>(); dfs(s, 0, new ArrayList<>(), res); return res; } private void dfs(String s, int start, List<String> parts, List<String> res) { int left = 4 - parts.size(); // 还需要切几段 if (left == 0) { if (start == s.length()) res.add(String.join(".", parts)); // 4 段刚好用完整个字符串 return; } int remain = s.length() - start; if (remain < left || remain > left * 3) return; // 剪枝：剩下的字符数必须在 [left, 3*left] 之间 for (int len = 1; len <= 3 && start + len <= s.length(); len++) { String seg = s.substring(start, start + len); if ((len > 1 && seg.charAt(0) == '0') || Integer.parseInt(seg) > 255) continue; // 不能有前导 0，数值不超过 255 parts.add(seg); dfs(s, start + len, parts, res); parts.remove(parts.size() - 1); } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl ["25525511135"] → ["255.255.11.135","255.255.111.35"] ["0000"] → ["0.0.0.0"] ["101023"] → ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] ["1111"] → ["1.1.1.1"] ["255255255255"] → ["255.255.255.255"] ["256256256256"] → []
Go · 解法代码func restoreIpAddresses(s string) []string { res := []string{} parts := []string{} var dfs func(start int) dfs = func(start int) { left := 4 - len(parts) // 还需要切几段 if left == 0 { if start == len(s) { // 4 段刚好用完整个字符串 res = append(res, strings.Join(parts, ".")) } return } remain := len(s) - start if remain < left || remain > left*3 { // 剪枝：剩下的字符数必须在 [left, 3*left] 之间 return } for length := 1; length <= 3 && start+length <= len(s); length++ { seg := s[start : start+length] v, _ := strconv.Atoi(seg) if (length > 1 && seg[0] == '0') || v > 255 { // 不能有前导 0，数值不超过 255 continue } parts = append(parts, seg) dfs(start + length) parts = parts[:len(parts)-1] } } dfs(0) return res }
$ go build -o bin . && ./bin < cases.jsonl ["25525511135"] → ["255.255.11.135","255.255.111.35"] ["0000"] → ["0.0.0.0"] ["101023"] → ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] ["1111"] → ["1.1.1.1"] ["255255255255"] → ["255.255.255.255"] ["256256256256"] → []
JavaScript · 解法代码function restoreIpAddresses(s) { const res = []; const parts = []; const dfs = (start) => { const left = 4 - parts.length; // 还需要切几段 if (left === 0) { if (start === s.length) res.push(parts.join(".")); // 4 段刚好用完整个字符串 return; } const remain = s.length - start; if (remain < left || remain > left * 3) return; // 剪枝：剩下的字符数必须在 [left, 3*left] 之间 for (let len = 1; len <= 3 && start + len <= s.length; len++) { const seg = s.substring(start, start + len); if ((len > 1 && seg[0] === "0") || Number(seg) > 255) continue; // 不能有前导 0，数值不超过 255 parts.push(seg); dfs(start + len); parts.pop(); } }; dfs(0); return res; }
$ node run.js < cases.jsonl ["25525511135"] → ["255.255.11.135","255.255.111.35"] ["0000"] → ["0.0.0.0"] ["101023"] → ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] ["1111"] → ["1.1.1.1"] ["255255255255"] → ["255.255.255.255"] ["256256256256"] → []
C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { void dfs(const string& s, int start, vector<string>& parts, vector<string>& res) { int left = 4 - (int)parts.size(); // 还需要切几段 if (left == 0) { if (start == (int)s.size()) { // 4 段刚好用完整个字符串 res.push_back(parts[0] + "." + parts[1] + "." + parts[2] + "." + parts[3]); } return; } int remain = (int)s.size() - start; if (remain < left || remain > left * 3) return; // 剪枝：剩下的字符数必须在 [left, 3*left] 之间 for (int len = 1; len <= 3 && start + len <= (int)s.size(); len++) { string seg = s.substr(start, len); if ((len > 1 && seg[0] == '0') || stoi(seg) > 255) continue; // 不能有前导 0，数值不超过 255 parts.push_back(seg); dfs(s, start + len, parts, res); parts.pop_back(); } } public: vector<string> restoreIpAddresses(string s) { vector<string> res, parts; dfs(s, 0, parts, res); return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl ["25525511135"] → ["255.255.11.135","255.255.111.35"] ["0000"] → ["0.0.0.0"] ["101023"] → ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] ["1111"] → ["1.1.1.1"] ["255255255255"] → ["255.255.255.255"] ["256256256256"] → []
共 16 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 16/16 Java 通过 16/16 Go 通过 16/16 JavaScript 通过 16/16 C++ 通过 16/16
Python 版本另外和三层循环枚举做了随机对拍：字符串长度 1 到 13，字符取自 0、1、2、5（这样前导 0、超过 255、长度不合适这几类情形都会经常出现）：
随机对拍 30000 组（长度 1 到 13、字符取自 0、1、2、5 的数字串（含前导 0、超过 255、长度不合适等情形）；结果按集合比较），solve 与 brute 的结果全部一致。
另外四种语言只在上面 16 组固定用例上验证过，没有做大规模随机对拍。这道题的搜索空间很小（最多 81 种切法），所以没有做规模对比实验。
下面的演示用 "101023"，共 5 个结果。可以看到几种情形：切满四段后还剩字符（失败）、剩下的字符数不在 [left, 3·left] 里（剪枝）、以及带前导 0 的段（如 "02"、"023"）被跳过。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的地址集合与 solve 的返回值一致。