93. 复原 IP 地址
题目描述
一个合法的 IP 地址由 4 个整数组成，中间用 '.' 隔开。每个整数在 0 到 255 之间，且不能有前导零，单独一个 0 可以。比如 "192.168.1.1" 合法，"0.011.255.245"、"192.168.1.312" 不合法。
输入只含数字的字符串 s。只允许在 s 里插入点号，不能调换顺序，也不能删除数字。
返回用这种方式能得到的全部合法 IP 地址，顺序不限。没有时返回空数组。
示例 1
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
解释：只有这两种切法能让四段都不超过 255。
示例 2
输入：s = "0000" 输出：["0.0.0.0"]
解释：每段只能是单个 0，因为 00 有前导零。
示例 3
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
解释：共有 5 种合法切法。
数据范围
1 <= s.length <= 20s只含数字。
解题思路
回溯切段：dfs(start) 从 start 开始切出长度 1–3 的一段。如果这段有前导零或大于 255，更长的段只会同样不合法，直接 break。切满 4 段时，只有刚好用完整个字符串才记录。
为什么正确
parts 中每一段都是合法的 0–255 整数且无前导零，且拼起来恰好是 s[0:start]。
复杂度分析
最多 3^4 = 81 种切法，时间 O(81 · |s|)，空间 O(1)。
易错点
切满 4 段但还有剩余字符时不能记录；"0" 合法但 "01" 不合法；切段长度不能超过剩余长度。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res, parts = [], []
def dfs(start):
if len(parts) == 4:
if start == len(s):
res.append('.'.join(parts))
return
for end in range(start + 1, min(start + 3, len(s)) + 1):
seg = s[start:end]
if (len(seg) > 1 and seg[0] == '0') or int(seg) > 255:
break
parts.append(seg)
dfs(end)
parts.pop()
dfs(0)
return resclass Solution {
String s;
List<String> res = new ArrayList<>(), parts = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
this.s = s;
dfs(0);
return res;
}
void dfs(int start) {
if (parts.size() == 4) {
if (start == s.length()) {
res.add(String.join(".", parts));
}
return;
}
for (int end = start + 1; end <= Math.min(start + 3, s.length()); end++) {
String seg = s.substring(start, end);
if ((seg.length() > 1 && seg.charAt(0) == '0') || Integer.parseInt(seg) > 255) {
break;
}
parts.add(seg);
dfs(end);
parts.remove(parts.size() - 1);
}
}
}class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> res, parts;
function<void(int)> dfs = [&](int start) {
if (parts.size() == 4) {
if (start == (int)s.size()) {
res.push_back(parts[0] + "." + parts[1] + "." + parts[2] + "." + parts[3]);
}
return;
}
for (int end = start + 1; end <= min(start + 3, (int)s.size()); end++) {
string seg = s.substr(start, end - start);
if ((seg.size() > 1 && seg[0] == '0') || stoi(seg) > 255) {
break;
}
parts.push_back(seg);
dfs(end);
parts.pop_back();
}
};
dfs(0);
return res;
}
};func restoreIpAddresses(s string) []string {
res, parts := []string{}, []string{}
var dfs func(start int)
dfs = func(start int) {
if len(parts) == 4 {
if start == len(s) {
res = append(res, strings.Join(parts, "."))
}
return
}
for end := start + 1; end <= min(start+3, len(s)); end++ {
seg := s[start:end]
v, _ := strconv.Atoi(seg)
if (len(seg) > 1 && seg[0] == '0') || v > 255 {
break
}
parts = append(parts, seg)
dfs(end)
parts = parts[:len(parts)-1]
}
}
dfs(0)
return res
}var restoreIpAddresses = function(s) {
const res = [], parts = [];
const dfs = (start) => {
if (parts.length === 4) {
if (start === s.length) {
res.push(parts.join('.'));
}
return;
}
for (let end = start + 1; end <= Math.min(start + 3, s.length); end++) {
const seg = s.slice(start, end);
if ((seg.length > 1 && seg[0] === '0') || Number(seg) > 255) {
break;
}
parts.push(seg);
dfs(end);
parts.pop();
}
};
dfs(0);
return res;
};function restoreIpAddresses(s: string): string[] {
const res: string[] = [], parts: string[] = [];
const dfs = (start: number): void => {
if (parts.length === 4) {
if (start === s.length) {
res.push(parts.join('.'));
}
return;
}
for (let end = start + 1; end <= Math.min(start + 3, s.length); end++) {
const seg = s.slice(start, end);
if ((seg.length > 1 && seg[0] === '0') || Number(seg) > 255) {
break;
}
parts.push(seg);
dfs(end);
parts.pop();
}
};
dfs(0);
return res;
}