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)
嗯，模拟和字符串分割。 利用temp[i]表示需要在i位置之前增加分割点。 这样会需要3个点。但是最后一个部分的数据合法情况需要提前进行判定。 也就是在记录step的时候，判断step==2的时候需要顺便判断最后一个数据的合法性。 每个大于0的数据不允许以0开头，IP的大<=255，IP每个字段的长度<=3，这些都是剪枝的条件。
class Solution { public: int n; string s; vector<string> restoreIpAddresses(string s) { vector<string> result; this->n=s.size(); //长度低于4的不可能被剖分成4个数字 if(n<4) return result; this->s=s; vector<int> temp;//总共只需要添加3个点 temp.push_back(0); dfs(temp,1,0,result); return result; } //IP地址的标准： //最多3位，不超过255 void dfs(vector<int> &temp,int start,int step,vector<string> &result){ //已经添加了3个点 if(step==3){ //将temp内节点依次取出，作为分隔点 string target=""; for(int i=1;i<4;i++){ target+=s.substr(temp[i-1],temp[i]-temp[i-1]); target+='.'; } target+=s.substr(temp[temp.size()-1],n-temp[temp.size()-1]); result.push_back(target); return; } //需要在1~n-1的位置添加点，在1的位置添加点表示s[0]和s[1]之间 for(int i=start;i<n;i++){ //不能超过3位 if(i-temp[temp.size()-1]<=3){ //并且在step=2(放最后一个点的时候)要照顾最后一位长度不能超过3 if(step==2 && n-i>3) continue; //求得此时的substr //从上一个结尾，到当前长度 string t=s.substr(temp[temp.size()-1],i-temp[temp.size()-1]); int val=atoi(t); //判断是否符合条件 if(val<=255){ if(step==2){ //检查最后一部分大小是否符合要求 string lastt=s.substr(i,n-i); if(atoi(lastt)>255) continue; } //记录切割的位置 temp.push_back(i); dfs(temp,i+1,step+1,result); temp.pop_back(); } } } } //字符串转数字 int atoi(string &str){ //不允许长度>0的部分以0开头 if(str[0]=='0' && str.size()>1) return 256; int sum=0; for(int i=0;i<str.size();i++){ sum=sum*10+str[i]-'0'; } return sum; } };