[93]复原 IP 地址

//给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。 
//
// 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。 
//
// 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 
//和 "192.168@1.1" 是 无效 IP 地址。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "25525511135"
//输出：["255.255.11.135","255.255.111.35"]
// 
//
// 示例 2： 
//
// 
//输入：s = "0000"
//输出：["0.0.0.0"]
// 
//
// 示例 3： 
//
// 
//输入：s = "1111"
//输出：["1.1.1.1"]
// 
//
// 示例 4： 
//
// 
//输入：s = "010010"
//输出：["0.10.0.10","0.100.1.0"]
// 
//
// 示例 5： 
//
// 
//输入：s = "101023"
//输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3000 
// s 仅由数字组成 
// 
// Related Topics 字符串 回溯算法 
// 👍 511 👎 0

/*
* 93 复原 IP 地址
* 2021-03-01 11:39:13
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<string> ans;
    string path;
    vector<string> restoreIpAddresses(string s) {
        if(s.empty() || s.size() > 12) return {};
        dfs(s, 0, 0);
        return ans;
    }

    void dfs(string& s, int idx, int cnt){
        if(cnt == 4 && idx >= s.size()){
            ans.push_back(path);
            return ;
        }

        for(int len = 1;len <= 3 && idx + len <= s.size();len++){
            string cur = s.substr(idx, len);
            if(cur.size() > 1 && cur[0] == '0') continue; // 一个0是可以的
            int num = stoi(cur);

            if(num >= 0 && num <= 255){
                string temp = path;
                path += s.substr(idx, len);
                if(idx + len != s.size()) path += '.';
                dfs(s, idx + len, cnt + 1);
                path = temp;
            }
        }
    }
};
//leetcode submit region end(Prohibit modification and deletion)