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

糖逗

题目描述：

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。

 

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    void dfs(string& s, int cur, vector<string>&temp, vector<string>& res){
        if(cur > s.size() || temp.size() > 4 || (cur >= s.size() && temp.size() < 4)) return;
        if(temp.size() == 4){
            if(cur == s.size()){
                string store;
                for(auto cha : temp) store = store + cha + ".";
                res.push_back(store.substr(0, store.size() - 1));
            }
            return;
        }
        vector<string> store1 = {s.substr(cur, 1), s.substr(cur, 2), s.substr(cur, 3)};
        for(int i = 0; i < 3; i++){
            if(store1[i][0] == '0' && store1[i].size() > 1) continue;
            if(stoi(store1[i]) <= 255){
                temp.push_back(store1[i]);
                dfs(s, cur + i + 1, temp, res);
                temp.pop_back();
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        vector<string> temp;
        dfs(s, 0, temp, res);
        return res; 
    }
};