题目描述

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

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

样例

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

算法分析

一共有4位数字，暴力枚举4个在[0,255]区间合法数字，若当前枚举的数字符合条件，则从下一个位置开始枚举下一个数字

时间复杂度 $O(C_{n - 1}^3)$

共有n个数字，从n - 1个间隔中取3个间隔点，因此时间复杂度是$O(C_{n - 1}^3)$

Java 代码

class Solution {
    static List<String> ans = new ArrayList<String>();

    static void dfs(String s,int u,int k,String path)
    {
        if(u == s.length())
        {
            if(k == 4)
            {
                ans.add(path.substring(0,path.length() - 1));//去掉"."号
            }
            return ;
        }

        if(k == 4) return ;

        for(int i = u,t = 0;i < s.length();i ++)
        {
            if(i > u && s.charAt(u) == '0') break;//前导0
            t = t * 10 + s.charAt(i) - '0';
            if(t <= 255) dfs(s,i + 1,k + 1,path + t + ".");
            else break;
        }
    }
    public List<String> restoreIpAddresses(String s) {
        ans.clear();
        dfs(s,0,0,"");
        return ans;
    }
}