93.复原-ip-地址

递归回溯在i位置分割还是不分割, 最后一个节点一定要分割, 有前导0不能不分割 @param s @return

class Solution {

    List<String> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>(4);

    /**
     * 递归回溯在i位置分割还是不分割,
     * 最后一个节点一定要分割, 有前导0不能不分割
     * @param s
     * @return
     */
    public List<String> restoreIpAddresses(String s) {
        int len = s.length();
        if (len > 12 || len < 4) return List.of();
        dfs(s, 0,  0);
        return ans;
    }

    /**
     *
     * @param s String
     * @param i 当前所在的位置, 在第i个字符的后面插入一个 '.'
     * @param num 前一个 . 到当前遍历的数字已经积累了大小多少的数字, 如果 > 255了则要return
     */
    private void dfs(String s, int i, int num) {
        if (path.size() == 4 && i == s.length()) {
            StringBuilder curr = new StringBuilder();
            curr.append(path.get(0));
            for (int j = 1; j < 4; j++) {
                curr.append('.');
                curr.append(path.get(j));
            }
            ans.add(curr.toString());
            return ;
        }

        if (path.size() == 4 || i == s.length()) return ;

        num = num * 10 + s.charAt(i) - '0';
        if (num > 255) return ;

        path.add(num);
        dfs(s, i+1, 0);
        path.remove(path.size() - 1);

        // 没有前导0, 才能不分割
        if (num > 0)
            dfs(s, i+1, num);
    }
}