Description
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
思路
- 回溯，每一次选择一个合适的数，然后进入下一次回溯，并且同时记录part，即IP的第几段。
代码
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
backtrack(s, 0, 0);
return res;
}
void backtrack(string s, int start, int part){
if(start == s.size() && part == 4){
res.push_back(str);
return;
}
for(int i = start; i < s.size(); ++i){
if(part < 4 && i - start < 3 && isValidIp(s, start, i)){
str.append(s.substr(start, i - start + 1));
part++;
if(part < 4) str.push_back('.');
backtrack(s, i + 1, part);
if(part < 4) str.pop_back();
part--;
for(int j = 0; j < i - start + 1; ++j)
str.pop_back();
}
}
}
bool isValidIp(string s, int start, int end){
string tmp = s.substr(start, end - start + 1);
int ip = stoll(tmp);
if(s[start] == '0' && start != end) return false;
else if(ip >= 0 && ip <= 255) return true;
return false;
}
private:
vector<string> res;
string str;
};