题解 | #数字字符串转化成IP地址#

java dfs+回溯

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    static ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        dfs(0,s,new ArrayList<String>());
        return res;
    }
    public void dfs(int u, String str, ArrayList<String> list) {
        if(u == str.length() && list.size() == 4){
            String st = "";
            for(int i = 0;i < list.size() - 1;i++){
                st += list.get(i) + ".";
            }
            st += list.get(list.size() - 1);
            res.add(st);
            return;
        }
        if(u > str.length()) {
            return;
        }
        for(int i = 1;i <= 3;i++){
            if(u + i <= str.length()){
                String s1 = str.substring(u,u + i);
                int k = Integer.valueOf(s1);
                if(k > 255 || (k == 0  && s1.length() > 1) || (s1.length() > 1 && s1.charAt(0) == '0') ){
                    continue;
                }
                list.add(s1);
                dfs(u + i,str,list);
                list.remove(list.size() - 1);
            }

        }

    }

}