题目描述

给定一个字符串，只包含数字。请解码出所有合法的IP地址。

样例

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

算法

(暴力搜索) $O(C_{n-1}^3)$

直接暴力搜索出所有合法方案。
合法的IP地址由四个0到255的整数组成。我们直接枚举四个整数的位数，然后判断每个数的范围是否在0到255。

时间复杂度分析：一共 $n$ 个数字，$n-1$ 个数字间隔，相当于从 $n-1$ 个数字间隔中挑3个断点，所以计算量是 $O(C_{n-1}^3)$。

C++ 代码

class Solution {
public:
    vector<string> ans;
    vector<int> path;

    vector<string> restoreIpAddresses(string s) {
        dfs(0, 0, s);
        return ans;
    }

    // u表示枚举到的字符串下标，k表示当前截断的IP个数，s表示原字符串
    void dfs(int u, int k, string &s)
    {
        if (u == s.size())
        {
            if (k == 4)
            {
                string ip = to_string(path[0]);
                for (int i = 1; i < 4; i ++ )
                    ip += '.' + to_string(path[i]);
                ans.push_back(ip);
            }
            return;
        }
        if (k > 4) return;

        unsigned t = 0;
        for (int i = u; i < s.size(); i ++ )
        {
            t = t * 10 + s[i] - '0';
            if (t >= 0 && t < 256)
            {
                path.push_back(t);
                dfs(i + 1, k + 1, s);
                path.pop_back();
            }
            if (!t) break;
        }
    }
};