?做题思路or感想
这种字符串切割的问题都可以用回溯法来解决
【93.|93. 复原 IP 地址】递归三部曲：
- 递归参数
- 因为要切割字符串，所以要用一个
startIndex来控制子串的开头位置，即是会切割出一个范围是[startIndex, i]的子串
- 因为要切割字符串，所以要用一个
- 递归中止条件
- 这里因为IP地址有正好四个整数（子串）构成，所以当切割的子串数量为4时就可以了。然后因为这四个子串组合起来要正好是主串，所以还需要
startIndex超过主串的最后一位，即s.size() - 1才行
- 这里因为IP地址有正好四个整数（子串）构成，所以当切割的子串数量为4时就可以了。然后因为这四个子串组合起来要正好是主串，所以还需要
- 递归单层逻辑
- 判断子串是否符合条件，符合后便把子串放入
vector中
- 判断子串是否符合条件，符合后便把子串放入
- 判断条件
- 不能有前导0
- 子串长度不超过3
- 不能有除了数字外的其他字符
- 子串转化成的数字范围要在
[0, 255]中
class Solution {
public:
vectorresult;
vectortemp;
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 restoreIpAddresses(string s) {
dfs(s, 0);
return result;
}
};
