- 输入：s = "25525511135"
- 输出：["255.255.11.135","255.255.111.35"]
建议先看分割回文串，再学习此算法
注意点：
- 题目要求result是vector<string>类型，和之前不同，需要注意，path如果也还是vector<string>类型，最终结果怎么组合。
- 怎么判断一个字符串是否合法，怎么将一个字符串转化为整数（循环转化）。如果不使用该方法，直接使用stoi（s）转化也可以。
- 不要忘记递归深度。
1.
path数组里面存储的是分割后的字符串，最后拼接在一起。这里的path.size() == 4 就限制了递归深度只能为4，即只能分割为四个字符串。
if (path.size() == 4 && startIndex == s.size()) { // 拼接成一个完整的IP地址字符串 string ipAddress = path[0] + "." + path[1] + "." + path[2] + "." + path[3]; result.push_back(ipAddress); return; }2.
循环验证每个字符时候合法（1-9），并且将数字字符串转化为整数。
for(int i = 0; i < s.size(); i ++){ // 3.1 检查是否是数字字符 if(s[i] > '9' || s[i] < '0') return false; // 3.2 将字符转换为数字并累加 // 例如："123"的处理过程： // i=0: num = 0*10 + 1 = 1 // i=1: num = 1*10 + 2 = 12 // i=2: num = 12*10 + 3 = 123 num = num * 10 + (s[i] - '0'); // 3.3 实时检查是否超过255，避免溢出问题 if(num > 255) return false; }解决以上注意点，基本没什么难度了。
代码
#include<iostream> #include<vector> #include<string> // 引入string库以使用stoi using namespace std; class Solution { private: // result: 用于存储所有有效的、格式化后的IP地址 vector<string> result; // path: 用于存储当前正在构造的IP地址的四个分段 vector<string> path; // 核心的回溯函数 // s: 输入的原始数字字符串 // startIndex: 当前准备为哪个分段截取数字的起始索引 void backtracking(const string& s, int startIndex) { // 终止条件1：如果已经找到4个分段，并且所有字符都用完了 if (path.size() == 4 && startIndex == s.size()) { // 拼接成一个完整的IP地址字符串 string ipAddress = path[0] + "." + path[1] + "." + path[2] + "." + path[3]; result.push_back(ipAddress); return; } // 终止条件2（剪枝）：如果分段数已达4个但字符串未用完，或字符串用完但分段不足4个 if (path.size() == 4 || startIndex == s.size()) { return; } // 单层搜索：尝试截取1到3位数字作为当前分段 for (int i = startIndex; i < s.size(); i++) { // 截取 [startIndex, i] 之间的子串作为IP地址的一个分段 string segment = s.substr(startIndex, i - startIndex + 1); // 检查该分段是否有效 if (isValid(segment)) { path.push_back(segment); // 选择：将有效分段加入路径 backtracking(s, i + 1); // 递归：处理下一个分段 path.pop_back(); // 回溯：撤销选择 } else { // 剪枝：如果当前分段已无效（如"01", "256"）， // 那么任何包含它的更长分段（"010", "2561"）也必然无效， // 所以直接中断当前循环。 break; } } } // 判断一个字符串是否是合法的IP地址段（0-255） bool isValid(const string& s){ // 1. 长度检查：IP段长度不能超过3位 if (s.size() > 3) return false; // 2. 前导零检查：如果长度大于1且第一个字符是'0'，则为非法（如"01"、"001"） if (s.size() > 1 && s[0] == '0') return false; int num = 0; // 用于累加计算的数值 // 3. 逐字符检查并转换为数字 for(int i = 0; i < s.size(); i ++){ // 3.1 检查是否是数字字符 if(s[i] > '9' || s[i] < '0') return false; // 3.2 将字符转换为数字并累加 // 例如："123"的处理过程： // i=0: num = 0*10 + 1 = 1 // i=1: num = 1*10 + 2 = 12 // i=2: num = 12*10 + 3 = 123 num = num * 10 + (s[i] - '0'); // 3.3 实时检查是否超过255，避免溢出问题 if(num > 255) return false; } // 原始代码中被注释掉的 stoi(s) > 255 是另一种实现方式 // 但当前实现更安全，避免了字符串转整数的异常 return true; // 所有检查通过，是合法的IP段 } public: // 主函数，用于恢复IP地址 vector<string> restoreIpAddresses(string s) { result.clear(); path.clear(); // 剪枝：如果字符串长度不足4或超过12，不可能组成有效IP if (s.size() < 4 || s.size() > 12) { return result; } backtracking(s, 0); return result; } }; int main() { Solution S; string s = "0000"; vector<string> result = S.restoreIpAddresses(s); // 遍历并打印所有有效的IP地址 for (const auto& ip : result) { cout << ip << endl; } return 0; }
