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)
用C++写的，暴力搜索，加上限制条件，以后考虑是否有改进的地方，这个题目的搜索空间较小、限制条件多，运行速度也很快
class Solution { public: vector<string> restoreIpAddresses(string s) { int length = 0; vector<string> vs; length = s.size(); int a = 1 , b = 1 , c = 1 , d = 1; int tok = 0; int tmp = 0; for(a=1;a<4;a++){ if(s[0]==‘0‘ && a>1) break; for(b=1;b<4;b++){ if(s[a]==‘0‘ && b>1) break; if(a==3){ if(s[0]!=‘2‘ && s[0]!=‘1‘){ break; } tmp = (s[1]-‘0‘); if(tmp > 5 && s[0] == ‘2‘) break; } for(c=1;c<4;c++){ if(s[a+b]==‘0‘ && c>1) break; if(b==3){ if(s[a]!=‘2‘&&s[a]!=‘1‘) break; tmp = (s[a+1]-‘0‘); if(tmp > 5 && s[a] == ‘2‘) break; } for(d=1;d<4;d++){ if(s[a+b+c]==‘0‘ && d>1) break; if(c==3){ if(s[a+b]!=‘2‘&&s[a+b]!=‘1‘) break; tmp = (s[a+b+1] - ‘0‘); if(tmp > 5 && s[a+b] == ‘2‘) break; } if((a+b+c+d)==length){ tok = stoi(s.substr(a+b+c,d)); if(tok>255) break; string rt = s.substr(0,a) + "." + s.substr(a,b) + "." + s.substr(a+b,c) + "." + s.substr(a+b+c,d); vs.push_back(rt); } } } } } return vs; } };
原文：http://www.cnblogs.com/hitnoah/p/4241536.html