做题思路or感想
这种字符串切割的问题都可以用回溯法来解决
递归三部曲：
递归参数
因为要切割字符串，所以要用一个startIndex来控制子串的开头位置，即是会切割出一个范围是[startIndex, i]的子串
递归中止条件
这里因为IP地址有正好四个整数（子串）构成，所以当切割的子串数量为4时就可以了。然后因为这四个子串组合起来要正好是主串，所以还需要startIndex超过主串的最后一位，即s.size() - 1才行
递归单层逻辑
判断子串是否符合条件，符合后便把子串放入vector<string>中
判断条件
- 不能有前导0
子串长度不超过3
不能有除了数字外的其他字符
子串转化成的数字范围要在
[0, 255]中class Solution {
public:
vector<string>result;
vector<string>temp;
bool isGood(string s, int startIndex, int i) {
//子串长度限制
if (i - startIndex + 1 >= 4)return false;
string str = s.substr(startIndex, i - startIndex + 1);
//由子串转化成的数字的范围的限制
if (0 > stoi(str) || stoi(str) > 255)return false;
//前导0的限制
if (str.size() > 1 && str[0] == '0')return false;
//非法字符的限制
for (int j = 0; j < str.size(); j++) {
if (str[j] >= '0' && str[j] <= '9')continue;
else return false;
}
return true;
}
void dfs(string s, int startIndex) {
//递归中止条件
if (temp.size() == 4 && startIndex >= s.size()) {
string str;
//需要把子串拿出来做一点加工后再放到result中！！！
for (int i = 0; i < temp.size(); i++) {
if (i != temp.size() - 1) {
str = str + temp[i] + ".";
} else {
str = str + temp[i];
}
}
result.push_back(str);
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isGood(s, startIndex, i)) {
string str = s.substr(startIndex, i - startIndex + 1);
temp.push_back(str);
dfs(s, i + 1);
temp.pop_back(); //回溯
}
}
}
vector<string> restoreIpAddresses(string s) {
dfs(s, 0);
return result;
}
};
