思路：遞歸+回溯+剪枝（valid判斷）
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> res;
if(s.length()<4)
return res;
backtracking(0,"",res,s,1);
return res;
}
void backtracking(int begin,string tmp, vector<string>& res, string s,int index)
{
if(index==5)
{
if(begin==s.length())
{
res.push_back(tmp);
}
return;
}
for(int i=begin;i<begin+3 && i<s.length();i++)
{
string r=s.substr(begin,i-begin+1);
if(valid(r))
{
if(index<4)
r=r+'.';
backtracking(i+1,tmp+r,res,s,index+1);
}
continue;
}
}
bool valid(string s)
{
if(s.length()>1 && s[0]=='0')
return false;
if(stoi(s)>255)
return false;
return true;
}
};
