1、前言

2、思路

这道题使用回溯的思路去做，一开始的时候不要想着使用一个字符串临时变量去拼接，因为最后一个 "." 号处理繁琐。最优雅的方式是使用 list 记录总共要添加的字符串，最后用 "." 连接。因为 ip 地址分为4段，所以长度为4的时候则加入到集合中，这意味着符合条件时树最多有4层。

针对 ip 地址的特殊性，判断一下每次要分的字符够不够或者是不是多了。如果符合条件，针对每层，做 left 开始 1 到 3个进行选取判断 ip 是否有效，有效则继续进入树的下一层，即下一个 ip 段的选取。

这个题目的判断还是很繁琐的。。。

3、代码

class Solution {

    List<String> res = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if(s == null || s.length() < 4 || s.length() > 12){
            return new ArrayList<>();
        }

        List<String> path = new ArrayList<>();
        dfs(s, 0, 0, path);

        return res;
    }

    private void dfs(String s, int splitTimes, int left, List<String> path){
        if(left == s.length()){
            if(splitTimes == 4){
                res.add(path.stream().collect(Collectors.joining(".")));
            }
            return;
        }

        // 如果剩下的字符不够切（取最小的），或者剩下的字符比需要的还多，则退出
        if(s.length() - left < (4 - splitTimes) || s.length() - left > 3 * (4 - splitTimes)){
            return;
        }

        // 只会有三个数字
        for(int i = 0; i < 3; i++){
            // 都是按照每段3个来处理，万一处理到最后一段，小于3个的情况，如果到2大于 s 的长度，直接退出
            if(left + i >= s.length()){
                continue;
            }

            // subString 要多加一位
            String str = s.substring(left, left + i + 1);
            if(!isValid(str)){
                continue;
            }
            path.add(str);
            dfs(s, splitTimes + 1, left + i + 1, path);
            path.remove(path.size() - 1);
        }
    }

    private boolean isValid(String str){
        if((str.length() > 1 && str.charAt(0) == '0') || str.length() > 3){
            return false;
        }

        int num = Integer.parseInt(str);
        if(num < 0 || num > 255){
            return false;
        }

        return true;
    }
}