今日算法（回溯找IP，加检测）

题目描述

给定一个只包含数字的字符串s，用它来表示一个 IP 地址，返回所有可能的有效 IP 地址。

有效 IP 地址规则

1. 由4 段整数组成，每段用.分隔。
2. 每段整数的取值范围：0 ~ 255。
3. 每段整数不能有前导 0（除非该段本身就是 0，如0是合法的，01不合法）。
4. 不能重新排序或删除s中的任何数字。

示例 1：

• 输入：s = "25525511135"
• 输出：["255.255.11.135","255.255.111.35"]

示例 2：

• 输入：s = "0000"
• 输出：["0.0.0.0"]

核心思路：回溯法

IP 地址需要被分成 4 段，每段长度为 1~3 位数字，且满足上述规则。我们可以用回溯法枚举所有可能的分割方式，同时用剪枝排除无效分支。

回溯三要素

1. 选择：在当前位置，选择截取 1 位、2 位或 3 位数字作为一段。
2. 限制（剪枝）：
   • 截取的子串长度不能超过 3，也不能超出字符串末尾。
   • 子串代表的数字必须在0~255之间。
   • 子串长度大于 1 时，不能以'0'开头（前导 0 非法）。
3. 结束条件：已经分割出 4 段，且用完了所有字符，将当前方案加入结果集。

完整代码实现（C++）

#include <vector> #include <string> using namespace std; class Solution { public: vector<string> restoreIpAddresses(string s) { vector<string> result; vector<string> path; // 保存当前分割的4段 backtrack(s, 0, path, result); return result; } private: // start: 当前处理的起始位置 // path: 已经分割出的段 void backtrack(const string& s, int start, vector<string>& path, vector<string>& result) { // 终止条件：已经分割出4段，且用完了所有字符 if (path.size() == 4) { if (start == s.size()) { // 将4段用"."拼接成IP地址 string ip = path[0] + "." + path[1] + "." + path[2] + "." + path[3]; result.push_back(ip); } return; } // 枚举当前段的长度：1~3位 for (int len = 1; len <= 3; ++len) { // 剪枝1：超出字符串长度 if (start + len > s.size()) break; // 截取当前段 string segment = s.substr(start, len); // 剪枝2：前导0（长度>1且以'0'开头） if (len > 1 && segment[0] == '0') break; // 剪枝3：数值超过255 if (stoi(segment) > 255) break; // 选择当前段 path.push_back(segment); // 递归处理下一段 backtrack(s, start + len, path, result); // 回溯：撤销选择 path.pop_back(); } } };

代码逐行详解

1. 主函数与初始化

vector<string> restoreIpAddresses(string s) { vector<string> result; vector<string> path; backtrack(s, 0, path, result); return result; }

• result：存放所有合法的 IP 地址。
• path：存放当前正在构建的 4 段 IP 地址。
• 从start=0开始递归分割。

2. 终止条件

if (path.size() == 4) { if (start == s.size()) { string ip = path[0] + "." + path[1] + "." + path[2] + "." + path[3]; result.push_back(ip); } return; }

• 当path.size() == 4时，说明已经分割出 4 段。
• 此时需要start == s.size()，表示所有字符都已用完，这才是一个合法的 IP 地址。
• 不满足start == s.size()说明字符没用完，是无效分支，直接返回。

3. 枚举分割长度 + 剪枝

for (int len = 1; len <= 3; ++len) { // 剪枝1：超出字符串长度 if (start + len > s.size()) break; string segment = s.substr(start, len); // 剪枝2：前导0（长度>1且以'0'开头） if (len > 1 && segment[0] == '0') break; // 剪枝3：数值超过255 if (stoi(segment) > 255) break; // ... 递归与回溯 }

• len表示当前段的长度，只能是 1~3 位。
• 剪枝 1：如果start + len超出字符串长度，直接 break（更长的len也会超出，无需继续循环）。
• 剪枝 2：如果段长度大于 1 且以'0'开头（如"01"），不合法，直接 break。
• 剪枝 3：段的数值超过 255（如"256"），不合法，直接 break。

4. 递归与回溯

path.push_back(segment); backtrack(s, start + len, path, result); path.pop_back();

• path.push_back(segment)：将当前合法的段加入路径。
• backtrack(s, start + len, path, result)：递归处理下一段，起始位置变为start + len。
• path.pop_back()：回溯，撤销当前段，尝试下一种长度。

示例推演（以s = "25525511135"为例）

第一步：分割第一段

• len=1："2"，合法 → 递归处理start=1
• len=2："25"，合法 → 递归处理start=2
• len=3："255"，合法 → 递归处理start=3

重点分支：第一段为"255"（start=3）

第二步：分割第二段（start=3）

• len=1："2"，合法 → 递归处理start=4
• len=2："25"，合法 → 递归处理start=5
• len=3："255"，合法 → 递归处理start=6

分支：第二段为"255"（start=6）

第三步：分割第三段（start=6）

• len=1："1"，合法 → 递归处理start=7
• len=2："11"，合法 → 递归处理start=8
• len=3："111"，合法 → 递归处理start=9

分支 1：第三段为"11"（start=8）

• 第四段截取len=3："135"（数值 135 ≤ 255，合法）
• 四段为["255","255","11","135"]→ 拼接为"255.255.11.135"，加入结果。

分支 2：第三段为"111"（start=9）

• 第四段截取len=2："35"（数值 35 ≤ 255，合法）
• 四段为["255","255","111","35"]→ 拼接为"255.255.111.35"，加入结果。

复杂度分析

• 时间复杂度：\(O(3^4 \times n) = O(1)\)（常数级）
  • 每段有 3 种长度选择，共 4 段，最多 \(3^4=81\) 种分割方案。
  • 每个方案需要 \(O(n)\) 时间拼接 IP 地址（\(n \leq 12\)，实际影响可忽略）。
• 空间复杂度：\(O(4) = O(1)\)
  • 递归栈深度为 4（分割 4 段），path数组长度为 4，均为常数级。

关键知识点总结

1. 核心思想：用回溯法枚举所有分割方案，用剪枝排除无效分支。
2. 三大剪枝技巧：
   • 长度剪枝：段长度 1~3，且不超出字符串末尾。
   • 前导 0 剪枝：长度 > 1 时不能以'0'开头。
   • 数值剪枝：段的数值必须 ≤ 255。
3. 终止条件：分割出 4 段且用完所有字符。