剑指 Offer II 087. 复原 IP

这题坑特别多，主要有以下几点：

1. 边界问题，dot 数量按增加来操作，当 dot == 3 时就可以判断末尾字符串是否符合要求，如果符合，就收集即可。当 dot > 3 时，需要 return。

2. 当使用 StringBuilder 存储字符时，需要注意回溯时将 . 移除，但是在收集过程中回溯时则不需要将 . 移除。

   class Solution {
    List<String> res;
    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() == 0) return new ArrayList<>();
        res = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        backTracking(s, 0, 0, path);
        return res;
    }
    private void backTracking(String s, int pos, int dot, StringBuilder path) {
        // System.out.println(String.format("dot: %s, pos: %s", dot, pos));
        if (dot > 3) return;
        if (dot == 3) {
            // 收集
            // 判断第四段是否合法
            String sub = s.substring(pos, s.length());
            if (isValid(sub)) {
                path.append(sub);
                res.add(path.substring(0, path.length()));
                path.setLength(path.length() - sub.length());
            }
            return;
        }
        for (int i = pos; i < s.length(); i++) {
            String sub = s.substring(pos, i + 1);
            if (!isValid(sub)) break;
            path.append(sub).append(".");
            backTracking(s, i + 1, dot + 1, path);
            path.setLength(path.length() - 1 - sub.length());
        }
    }
    private boolean isValid(String s) {
        // 首位 0
        int len = s.length();
        if (len == 0) return false;
        if (s.charAt(0) == '0' && len > 1 ) return false;
        if (len > 3) return false;
        if (Integer.parseInt(s) > 255) return false;
        return true;
    }
   }