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

java版——回溯
常规版回溯，通俗易懂

public class Solution {

    ArrayList<String> res = new ArrayList<>(); // 存放结果集
    ArrayList<String> ipset = new ArrayList<>(); // 存放每一种合法的ip子集
    public ArrayList<String> restoreIpAddresses (String s) {
        int len = s.length();
        if(len < 4 || len > 12){ // 剪枝，ip最短为0.0.0.0，最长为255.255.255.255
            return res;
        }
        recall(s, 0, len);
        return res;
    }
    
    private void recall(String s, int index, int len){
        if(index == len && ipset.size() == 4){
            String ip = String.join(".", ipset);
            res.add(ip);
            return;
        }
        if(index == len || ipset.size() == 4){
            return;
        }
        int n = Math.min(index + 3, len); // 这里比较关键，保证ip地址每一段不能超过3
        for(int i = index; i < n; i++){
            String sub = s.substring(index, i + 1);
            // 剪枝，大于255或首位为0不合法
            if(Integer.parseInt(sub) > 255 || sub.length() > 1 && sub.charAt(0) == '0'){
                continue;
            }
            ipset.add(sub);
            recall(s, i + 1, len);
            ipset.remove(ipset.size() - 1);
        }
    }
}