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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        int n = s.length();
        dfs(result, list, n);
        ArrayList<String> res = new ArrayList<>();

        for (List<Integer> integers : result) {
            StringBuilder sb = new StringBuilder();
            int index = 0;
            boolean match = true;
            for (int j = 0; j < integers.size(); j++) {
                String substring = s.substring(index, index + integers.get(j));
                if (substring.startsWith("0") && substring.length() > 1) {
                    match = false;
                    break;
                }
                int integer = Integer.parseInt(substring);
                if (integer > 255) {
                    match = false;
                    break;
                }
                sb.append(integer).append(".");
                index += integers.get(j);
            }
            if (match) {
                res.add(sb.substring(0, sb.length() - 1));
            }

        }
        return res;
    }


    public static void dfs(List<List<Integer>> result, List<Integer> list, int n) {
        if (n < 1) {
            return;
        }
        if (list.size() > 3) {
            return;
        }

        if (n <= 3 && list.size() == 3) {
            list.add(n);
            result.add(new ArrayList<>(list));
            list.remove(list.size() - 1);
            return;
        }

        for (int i = 1; i < 4; i++) {
            list.add(i);
            dfs(result, list, n - i);
            list.remove(list.size() - 1);
        }
    }
}