代码随想录算法训练营第二十三天| 93.复原IP地址 78.子集 90.子集II

 1 //根据给定的一组字符串，分出来可能正确的IP
 2 //思路：切割，[start, i]，其中长度为0-3，
 3 //判断是否满足条件：0后面不可以有任何数字
 4 //终止条件：如果startIndex == 最后 并且path的长度为4，那么 就把所有的vector<string>path，合并在一起，组成string，放进result中
 5 bool isLegalIp(string s)
 6 {
 7     //最大值为255
 8     if (*s.begin() == '0' && s.size() > 1)
 9     {
10         return false;
11     }
12     if (stoi(s) > 255)
13     {
14         return false;
15     }
16 
17     return true;
18 }
19 
20 void restoreIpAddresses_trackBack(string s, int startIndex, vector<string>& path, vector<string>& result)
21 {
22     if (path.size() == 4 && startIndex == s.size())
23     {
24         string re_;
25         for (string val_ : path)
26         {
27             re_ += val_ + '.';
28         }
29         re_.pop_back();
30         result.push_back(re_);
31         return;
32     }
33     else if (path.size() == 4 && startIndex != s.size())
34     {
35         return;
36     }
37 
38     for (int i = startIndex; i < s.size()&&(i-startIndex)<=2; i++)
39     {
40         string cur_(s.begin() + startIndex, s.begin() + i + 1);
41         if (isLegalIp(cur_))
42         {
43             path.push_back(cur_);
44             restoreIpAddresses_trackBack(s, i + 1, path, result);
45             path.pop_back();
46         }
47     }
48 }
49 vector<string> restoreIpAddresses(string s) {
50     vector<string>result;
51     if (s.size() == 0) return result;
52     vector<string>path;
53     restoreIpAddresses_trackBack(s, 0, path, result);
54     return result;
55 }