93. 复原IP地址

 1 class Solution 
 2 {
 3     vector<string> res;
 4 public:
 5     vector<string> restoreIpAddresses(string s) 
 6     {
 7         string ip;//满足条件的IP地址
 8         helper(s, 0, ip);
 9         return res;
10     }
11 
12     void helper(string s, int n, string ip) //n为下标
13     {
14         if (n == 4) //下标为4且s变为空时
15         {
16             if (s.empty()) res.push_back(ip); 
17         }
18         else //否则
19         {
20             for (int k = 1; k < 4; ++k) //以点分割的字符长度为1,2,3
21             {
22                 //当前分割字符的长度大于当前的字符串，立马结束循环
23                 if (s.size() < k) break;
24                 int val = stoi(s.substr(0, k));
25                 //值大于255 或者 以0开头："01",可以剪枝
26                 if (val > 255  || k != to_string(val).size()) continue; 
27                 helper(s.substr(k), n + 1, ip + s.substr(0, k) + (n == 3 ? "" : "."));
28             }
29         }
30         return;
31     }
32 };