复原 IP 地址
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 是 无效 IP 地址。
给定一个只包含数字的字符串 s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任意 顺序返回答案。
示例 1
示例 2
示例 3
模拟答题者思考
1. 我先想暴力：在 s 的相邻字符间插入 3 个点，共有 C(n-1,3) 种切法，每种检查四段是否都在 0～255 且无前导零——思路对，但要把「切法枚举」写清楚。
2. 重复在哪里？很多切法在第一段就非法（如 "01"、"256"），却仍会继续枚举后面段的组合，浪费分支。
3. 关键转化：按从左到右顺序切四段，每段只可能是 1～3 个字符；用 segments 记录已切段，start 表示下一段起点——子问题变成「在 s[start:] 里再切 4 - len(segments) 段」。
4. 合法性一眼判断：len(seg)>1 and seg[0]=='0' 非法；int(seg)>255 非法；还剩 k 段时，剩余字符数必须在 [k, 3k] 之间，否则剪枝。
5. 例 s="25525511135"：第一段只能试 "2"/"25"/"255"，选 "255" 后递归；最终得到 255.255.11.135 与 255.255.111.35 两条合法路径。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
segments | list<str> | 定义：当前已切出的 IP 段（尚未加点拼接） 维护：DFS 每确定一段合法子串就 append，回溯时 pop更新：长度达到 4 且 start == len(s) 时，用 '.'.join(segments) 写入答案 |
start | int | 定义：下一段在 s 中的起始下标（含）维护：每选定长度为 len 的一段后，子问题从 start + len 继续更新：初始为 0；每成功切一段则前进；与 len(s) 对齐时才能收集四段解 |
seg | str | 定义：本轮尝试从 s[start:] 截取的长度为 1～3 的候选段维护：仅当通过合法性校验才进入递归 更新：每轮 for length in 1..3 生成；非法（前导零、>255、越界）直接 continue |
ans | list<str> | 定义：所有合法的四段 IP 字符串 维护：只在「恰好 4 段且用完整个 s」时追加更新：中途三段、或四段但还剩字符，均不收集 |
落码步骤
1. 初始化 ans = []，定义辅助函数 valid(seg)：长度 1～3、无前导零、数值 ≤ 255
2. 定义 DFS backtrack(start, segments)：若 len(segments) == 4，当且仅当 start == len(s) 时把 '.'.join(segments) 加入 ans，然后返回
3. 设还剩 remain = 4 - len(segments) 段；若剩余字符 len(s)-start 不在 [remain, 3*remain] 内，剪枝返回
4. 对 length 从 1 到 3：取 seg = s[start:start+length]，越界或 not valid(seg) 则跳过
5. segments.append(seg)，递归 backtrack(start + length, segments)，回溯 segments.pop()
6. 从 backtrack(0, []) 启动，返回 ans
代码实现
class Solution:
def restoreIpAddresses(self, s: str) -> list[str]:
ans: list[str] = []
n = len(s)
def valid(seg: str) -> bool:
if len(seg) > 1 and seg[0] == "0":
return False
return 0 <= int(seg) <= 255
def backtrack(start: int, segments: list[str]) -> None:
if len(segments) == 4:
if start == n:
ans.append(".".join(segments))
return
remain = 4 - len(segments)
rest = n - start
if rest < remain or rest > 3 * remain:
return
for length in range(1, 4):
if start + length > n:
break
seg = s[start : start + length]
if not valid(seg):
continue
segments.append(seg)
backtrack(start + length, segments)
segments.pop()
backtrack(0, [])
return ansclass Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> ans;
vector<string> segments;
int n = s.size();
auto valid = [](const string& seg) {
if (seg.size() > 1 && seg[0] == '0') return false;
int val = stoi(seg);
return val >= 0 && val <= 255;
};
function<void(int)> dfs = [&](int start) {
if ((int)segments.size() == 4) {
if (start == n) {
ans.push_back(segments[0] + "." + segments[1] + "." +
segments[2] + "." + segments[3]);
}
return;
}
int remain = 4 - (int)segments.size();
int rest = n - start;
if (rest < remain || rest > 3 * remain) return;
for (int len = 1; len <= 3; ++len) {
if (start + len > n) break;
string seg = s.substr(start, len);
if (!valid(seg)) continue;
segments.push_back(seg);
dfs(start + len);
segments.pop_back();
}
};
dfs(0);
return ans;
}
};
// 时间 O(1)（段数与每段长度有常数上界），空间 O(1) 递归栈复杂度分析
O(1)（至多 4 段、每段至多 3 种切分长度，与 |s|≤20 有常数上界；不计输出规模）
O(1)（递归深度 ≤ 4，不计输出）
常见坑
前导零：段 "01"、"00" 非法，但单字符 "0" 合法；必须写 len(seg)>1 and seg[0]=='0'，不能只判断数值。
四段未用完字符串：例如 s="1111" 切成四段 1.1.1.1 时 start 必须等于 n；若 segments.size()==4 但还有剩余字符，不能收集。
段长超过 3：IP 每段最多三位；循环 length 只取 1～3，且 int(seg)>255 时即使三位也要丢弃（如 "256"）。
必测边界 Case
s = "0000" → ["0.0.0.0"]（每段只能是单个 0）
s = "111" → []（至少 4 段、每段至少 1 字符，长度不足）
s = "25525511135" → 两组解，注意第三段可以是 11 或 111
s = "101023" → 5 组解，段长 1～3 混用