用c++写就是有点费力
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
int len = s.length();
if (len < 4 || len > 12) {
return {};
}
dfs(s, 0, ans);
return ans;
}
void dfs(string s, int index, vector<string>& ans) {
if (index == s.length() && tmp.size() == 4) {
string X = convert(tmp);
ans.push_back(X);
return;
}
int last = index + 3 > s.length() ? s.length() : index + 3;
for (int i = index; i < last; i++) {
string tmpString = s.substr(index, i - index + 1);
if (isValid(tmpString)) {
tmp.push_back(tmpString);
dfs(s, i + 1, ans);
tmp.pop_back();
}
}
}
string convert(vector<string> t) {
string s("");
for (string x: t) {
s += x;
s += ".";
}
s = s.substr(0, s.length() - 1);
return s;
}
bool isValid(string s) {
if (s.length() == 0) {
return false;
}
if (s.length() > 1 && s[0] == '0') {
return false;
}
int num = 0;
for (int i = 0; i < s.length(); i++) {
num = num * 10 + s[i] - '0';
}
if (num > 255) {
return false;
}
return true;
}
public:
vector<string> tmp;
vector<string> ans;
};
Processed:
0.009, SQL:
8
