1. 题目
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)
2. 思路
一共要提取出4个位域来。递归提取，每次从剩下的里面提取需要的个数，再讲当前合法的拼接上。
初始化点时当只需要提取一个时，直接用剩下的全部字符串匹配是否是有效的。注：前导0的形式是在题目里是认为不合法的，比如某一位是0、1、12都是ok的，但是00、01、001、012之类的是非法的。
3. 代码
class Solution {public: vector restoreIpAddresses(string s) { return getLeft(s, 0, 4); } // 从s[start->end]里提取cnt个ip域结果放到ips中 vector getLeft(string& s, int start, int cnt) { int len = s.length(); vector ips; if (cnt == 1) { if (valid(s, start)) { ips.push_back(s.substr(start)); } return ips; } for (int char_num = 1; char_num < 4; char_num++) { if (valid(s, start, char_num)) { string ip1 = s.substr(start, char_num) + "."; vector subs = getLeft(s, start+char_num, cnt-1); for (int i = 0; i < subs.size(); i++) { string ip2 = ip1 + subs[i]; ips.push_back(ip2); //cout << "s=" << s << " cnt=" << cnt << " ip=" << ip2 << endl; } } } return ips; } // s[start.. start+char_num-1]的是否是有效的 bool valid(string& s, int start, int char_num) { int len = s.length(); switch(char_num) { case 1 : return start < len; case 2 : return start < len - 1 && s[start] != '0'; case 3 : return valid3(s, start); default: return false; } } // [000-255] bool valid3(string&s, int start) { if (start < s.length() - 2) { int t = (s[start]-'0')*100 + (s[start+1]-'0')*10 + (s[start+2]-'0'); if (t >= 100 && t <= 255) { return true; } } return false; } // s[start->end]是否有效 bool valid(string&s , int start) { int len = s.length(); int char_num = len - start; if (char_num > 3 || char_num < 1) { return false; } int ip_num = 0; while (start < len) { ip_num = ip_num * 10 + s[start++] - '0'; } int min_ip = 0; if (char_num > 1) { min_ip = char_num == 2 ? 10 : 100; } if (ip_num >= min_ip && ip_num < 256) { return true; } return false; }};