Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"].
(Order does not matter)
思路：这是一道DFS题，在给字符串截取分配时，每次可以截一个、2个、三个，然后判断截取这三个是否满足ip的一个段，然后继续下一层。到达叶子节点时，需要判断ip段是否到达4并且字符串到达尾部，则从根节点到叶子节点是ip分段的一种。
class Solution {
private:
vector<string> res;
vector<string> perRes;
public:
int stringToInt(string s) {
int len = s.length();
int i,j=1,res=0;
for(i=len-1; i>=0; i--) {
res += (s[i]-'0')*j;
j *= 10;
}
return res;
}
string stringToIp(vector<string> aa)
{
int size = aa.size();
string str = "";
int i;
for(i=0; i<size; ++i)
{
str += aa[i];
if (i != size-1)
{
str += '.';
}
}
return str;
}
void restoreIpAddressesHelper(string s,int start, int end, int ipSeg) {
if (start >= end-1 && ipSeg == 4) {
res.push_back(stringToIp(perRes));
return;
}
if (start >= end-1 && ipSeg != 4) {
return;
}
if (start < end && ipSeg == 4) {
return;
}
int i, strInt,j;
for(j=1; j<=3; ++j)
{
if (start + j < end)
{
string str = s.substr(start+1,j);
strInt = stringToInt(str);
if ((j==1&&strInt>=0&&strInt<=9)||(j==2&&strInt>=10&&strInt<=99)||(j==3&&strInt>=100&&strInt<=255)) {
perRes[ipSeg] = str;
restoreIpAddressesHelper(s,start+j,end,ipSeg+1);
}
}
}
}
vector<string> restoreIpAddresses(string s) {
int len = s.length();
res.clear();
perRes.clear();
perRes.resize(4);
if (len < 4) {
return res;
}
restoreIpAddressesHelper(s,-1,len,0);
return res;
}
};