C++刷leetcode（93. 复原IP地址）【回溯】

糖逗

题目描述：

1. 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
   
2. 
   
3. 有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
   
4. 
   
5.  
   
6. 
   
7. 示例:
   
8. 
   
9. 输入: "25525511135"
   
10. 输出: ["255.255.11.135", "255.255.111.35"]
    
11. 
    
12. 来源：力扣（LeetCode）
    
13. 链接：https://leetcode-cn.com/problems/restore-ip-addresses
    
14. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     void dfs(string& s, int cur, vector<string>&temp, vector<string>& res){
   
4.         if(cur > s.size() || temp.size() > 4 || (cur >= s.size() && temp.size() < 4)) return;
   
5.         if(temp.size() == 4){
   
6.             if(cur == s.size()){
   
7.                 string store;
   
8.                 for(auto cha : temp) store = store + cha + ".";
   
9.                 res.push_back(store.substr(0, store.size() - 1));
   
10.             }
    
11.             return;
    
12.         }
    
13.         vector<string> store1 = {s.substr(cur, 1), s.substr(cur, 2), s.substr(cur, 3)};
    
14.         for(int i = 0; i < 3; i++){
    
15.             if(store1[i][0] == '0' && store1[i].size() > 1) continue;
    
16.             if(stoi(store1[i]) <= 255){
    
17.                 temp.push_back(store1[i]);
    
18.                 dfs(s, cur + i + 1, temp, res);
    
19.                 temp.pop_back();
    
20.             }
    
21.         }
    
22.     }
    
23.     vector<string> restoreIpAddresses(string s) {
    
24.         vector<string> res;
    
25.         vector<string> temp;
    
26.         dfs(s, 0, temp, res);
    
27.         return res;
    
28.     }
    
29. };

复制代码