Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input:"25525511135"Output:["255.255.11.135", "255.255.111.35"]
给定一组数字组成的字符串，要求输出所有的ip地址的可能。
IP地址一共有4位，每位由1-3个数字构成，范围是0-255，若某位是0，只能是“0”，而不能是“00”“000”。
public:
vector<string> restoreIpAddresses(string s) {
vector<string> res;
restore(s, 4, "", res);
return res;
}
void restore(string s, int k, string out, vector<string> &res){
if(k == 0){
if(s.empty()) res.push_back(out);
}
else{
for(int i=1; i<=3; i++){
if(s.size() >= i && isValid(s.substr(0, i))){
if(k == 1) restore(s.substr(i), k-1, out + s.substr(0, i), res);
else restore(s.substr(i), k-1, out + s.substr(0, i) + ".", res);
}
}
}
}
bool isValid(string s){
if(s.empty() || (s.size() >1 && s[0] == '0')) return false;
int res = atoi(s.c_str());
if(res>=0 && res<= 255) return true;
return false;
}
