输出一个数字串能生成的所有ip地址。注意0的情况
class Solution { public: vector<string> restoreIpAddresses(string s) { vector<string>ans; ans.clear(); if(s.length() > 12)return ans; vector<int>split; split.clear(); split.push_back(0); for(int i = 0;i < s.length();i++) { int num = genInt(split[split.size()-1],i,s); if(num >= 0&&num <= 255) { split.push_back(i); searchS(s,split,ans); split.pop_back(); } } return ans; } private: int genInt(int start,int end,string s) { string numstr(s,start,end-start+1); if(numstr.length() >= 4)return -1; if(end > start && s[start] == '0')return -1; int num = 0; bool flag = false; for(int i = numstr.length()-1;i >= 0;i--) { flag = true; num += (numstr[i] - '0')*(int)pow(10.0,(int)numstr.length() - 1 - i); } if(!flag)return -1; return num; } void searchS(string s,vector<int>&split,vector<string>&ans) { if(split.size() == 5) { string tmp = s; for(int i = 1;i < split.size()-1;i++) { tmp.insert(tmp.begin()+split[i]+i,'.'); } ans.push_back(tmp); return; } if(split.size() == 4) { int numlast = genInt(split[split.size()-1]+1,s.length()-1,s); if(numlast >= 0&&numlast <= 255) { split.push_back(s.length()-1); searchS(s,split,ans); split.pop_back(); } return; } for(int i = split[split.size()-1]+1;i < s.length();i++) { int num = genInt(split[split.size()-1]+1,i,s); if(num >= 0&&num <= 255) { split.push_back(i); searchS(s,split,ans); split.pop_back(); } } } };