算法1

(更加暴力枚举) $O(n^2)$

自己缕了一遍的递归搜索树

时间复杂度

参考文献

java 代码

class Solution {
    ArrayList<String> ans = new ArrayList<>();//存结果
    ArrayList<Integer> path = new ArrayList<>();//存过程
    public List<String> restoreIpAddresses(String s) {
        dfs(0,0,s);
        return ans;
    }
    public void dfs(int u ,int k,String s){
        //基线条件
        if(u>=s.length()) return;
         if(k==3)//剩下的字符串自成一组
        {
            if(s.charAt(u)=='0'&&u<s.length()-1) return;
            int t = 0;
            while(u<s.length()){t=t*10+(s.charAt(u++)-'0');}//把剩下的字符串变成int
            if(t>255||t<0) return;
            else{
                path.add(t);
                k++;
            }
        }
        if(k==4){
            //将path中的int输出
            String p =path.get(0).toString();
            for(int i = 1;i<path.size();i++){
                p+="."+path.get(i).toString();
            }
            ans.add(p);
            path.remove(3);
            return;
        }
        int cur=0;
        for(int i =0;i<=2&&u+i<s.length();i++){
            cur= cur*10+(s.charAt(u+i)-'0');
            if(cur>=0&&cur<=255)
            {
                path.add(cur);
                dfs(u+i+1,k+1,s);
                path.remove(k);
            }
            if(cur==0) return;
        }
    }
}