426-恢复IP地址
思路
使用递归+回溯，需要注意的是合法 ip 的判断，即：
- 每一节的数组均在 0 到 255 之间，包含 0 和 255
- 001，01 均是不合法的，但 0 ，10，100合法
- 共有4节，不多不少
code
class Solution {
public:
/*
* @param s: the IP string
* @return: All possible valid IP addresses
*/
vector<string> restoreIpAddresses(string s) {
// write your code here
if (s.size() < 4 || s.size() > 12) {
return vector<string>();
}
vector<string> result;
vector<string> temp;
restoreIpAddresses(s, result, temp, 0);
return result;
}
void restoreIpAddresses(string s, vector<string> &result, vector<string> &temp, int start) {
if (temp.size() == 4 && start == s.size()) {
result.push_back(temp[0] + "." + temp[1] + "." + temp[2] + "." + temp[3]);
return;
}
else if (temp.size() == 4 && start != s.size()) {
return;
}
for (int i = start; i < s.size() && i < start + 3; i++) {
if (isValid(s.substr(start, i - start + 1))) {
temp.push_back(s.substr(start, i - start + 1));
restoreIpAddresses(s, result, temp, i + 1);
temp.pop_back();
}
}
}
bool isValid(string s) {
if (s[0] == '0') {
return s == "0";
}
int digit = atoi(s.c_str());
return digit >= 0 && digit <= 255;
}
};