class Solution {
public:
vector<string> res;
int pointNum;
bool isValid(string s, int begin, int end) {
if (begin > end) return false; //防止在最后末尾插入.
if (s[begin] == '0' && begin != end) return false; //第一位为0且不止一位
int num = 0;
for (int i = begin; i <= end; i ++) {
if (s[i] > '9' && s[i] < '0') return false;
num = num * 10 + (s[i] - '0');
if (num > 255) return false;
}
return true;
}
void dfs(int start, string s) {
if (pointNum == 3) {
if (isValid(s, start, s.size() - 1)) { //判断最后子串是否合法
res.push_back(s);
}
return;
}
for (int i = start; i < s.size(); i ++) {
if (isValid(s, start, i)) {
s.insert(s.begin() + i + 1, '.');
pointNum ++;
dfs(i + 2, s);
s.erase(s.begin() + i + 1);
pointNum --;
}
else break;
}
}
vector<string> restoreIpAddresses(string s) {
dfs(0, s);
return res;
}
};
标签:begin,return,int,IP,pointNum,num,false,93,LeetCode
From: https://www.cnblogs.com/hjy94wo/p/16655272.html