给定一个只包含数字的字符串，复原它并返回所有可能的 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 仅由数字组成

Solution

• 回溯法，参考 代码随想录
• 转化到切割问题，其他相似题型 [131 分割回文串]

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        res.clear();
        backtrack(s, 0, 0);
        return res;
    }
private:
    vector<string> res;
    
    void backtrack(string& s, int index, int pointNum) {
        if (pointNum == 3) {
            // 判断第四段子字符串是否合法，如果合法就放进result中
            if (isValid(s, index, s.size() - 1)) {
                res.push_back(s);
            }
            return;
        }

        for (int i = index; i < s.size(); ++i) {
            if (isValid(s, index, i)) {
                s.insert(s.begin() + i + 1, '.');  // 插入分隔'.'
                pointNum++;
                backtrack(s, i + 2, pointNum);
                pointNum--;
                s.erase(s.begin() + i + 1);
            }
        }
        return;
    }

    // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
    bool isValid(const string& s, int start, int end) {
        if (start > end) return false;
        // 0 开头的数字不合法
        if (s[start] == '0' && start != end) return false;

        int num = 0;
        for (int i = start; i <= end; ++i) {
            if (s[i] > '9' || s[i] < '0') {
                return false;  // 非法字符
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) {
                return false;
            }
        }
        return true;
    }
};

• 回溯法，参考 liuyubobobo 的题解

// @lc code=start
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        vector<int> ip;
        dfs(s, 0, ip, res);
        return res;
    }

private:
    void dfs(const string& s, int index, vector<int>& ip, vector<string>& res){
        if(index==s.size()){
            if(ip.size()==4)
                res.push_back(get_string(ip));
            return;
        }
        if(index==0){
            ip.push_back(s[0]-'0');
            dfs(s, index+1, ip, res);
        }
        else{
            int next = ip.back()*10 + (s[index]-'0');
            // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if(next<=255 && ip.back()!=0){
                ip.back() = next;
                dfs(s, index+1, ip, res);
                ip.back() /= 10;
            }
            if(ip.size() < 4){
                ip.push_back(s[index]-'0');
                dfs(s, index+1, ip, res);
                ip.pop_back();
            }
        }
    }

    string get_string(const vector<int>& ip){
        string res = to_string(ip[0]);
        for(int i=1; i<ip.size(); ++i)
            res += "." + to_string(ip[i]);
        return res;
    }
};
// @lc code=end

• 暴力法，暴力美学。。。

class Solution {
public:
    bool checkValid(string s)
    {
        if (stoi(s) <= 255) {
            if (s[0] != '0' || (s[0] == '0' && s.size() == 1)) {
                return true;
            }
        }
        return false;
    }

    vector<string> restoreIpAddresses(string s)
    {
        vector<string> result;
        
        for(int a = 1 ; a < 4 ; ++ a)
            for(int b = 1 ; b < 4 ; ++ b)
                for(int c = 1 ; c < 4 ; ++ c)
                    for(int d = 1 ; d < 4 ; ++ d)
                    {
                        if(a + b + c + d == s.length() )
                        {
                            string s1 = s.substr(0, a);
                            string s2 = s.substr(a, b);
                            string s3 = s.substr(a+b, c);
                            string s4 = s.substr(a+b+c, d);
                            if(checkValid(s1) && checkValid(s2) && checkValid(s3) && checkValid(s4))
                            {
                                string validIp = s1 + '.' + s2 + '.' + s3 + '.' + s4;
                                result.push_back(validIp);
                            }
                        }
                    }
        return result;
    }
};