LeetCode:Restore IP Addresses

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的方式递归的计算，具体见代码注释本文地址

 1 class Solution { 
 2 public:
 3     vector<string> restoreIpAddresses(string s) {
 4         // IMPORTANT: Please reset any member data you declared, as
 5         // the same Solution instance will be reused for each test case.
 6         vector<string> res;
 7         string tmpres;
 8         restoreIpAddressesRecur(s, 0, 4, tmpres, res);
 9         return res;
10     }
11     //从s的start位置开始计算，ip地址还需要num个域（共4个域）
12     //tmpres表示当前计算好的部分ip
13     void restoreIpAddressesRecur(string &s, int start, int num, 
14         string &tmpres, vector<string> &res)
15     {
16         int len = s.size();
17         if(num == 0)
18         {
19             if(start == len)//已经计算好了一个ip
20             {
21                 tmpres.erase(--tmpres.end());//去掉最后的“.”
22                 res.push_back(tmpres);
23                 tmpres.push_back('.');
24             }
25             return;
26         }
27         //不满足最小或最大长度关系
28         if(len - start < num || len - start > num*3)return;
29         int tmplen = tmpres.size();
30         string tmpstr;
31         for(int i = 1; i <= 3 && start + i <= len; i++)
32         {//ip地址的一个域最多包含三个数字
33             if(validRegion(s, start, start+i-1) == false)continue;
34             tmpstr = s.substr(start, i) + ".";
35             tmpres += tmpstr;
36             restoreIpAddressesRecur(s, start+i, num-1, tmpres, res);
37             tmpres.erase(tmplen, i+1);
38         }
39     }
40     //判断ip地址的一个域是否合法
41     bool validRegion(string &s, int istart, int iend)
42     {
43         if(iend > istart && s[istart] == '0')return false;
44         int res = 0;
45         for(int i = istart; i <= iend; i++)
46             res = res*10 + (s[i] - '0');
47         if(res >= 0 && res <= 255)return true;
48         else return false;
49     }
50 };