// @Title: 复原 IP 地址 (Restore IP Addresses)
// @Author: qisiii
// @Date: 2024-09-20 10:47:39
// @Runtime: 1 ms
// @Memory: 41.3 MB
// @comment: 
// @flag: 
class Solution {
    public List<String> restoreIpAddresses(String s) {
        int step = s.length() / 4;
        List<String> result = new ArrayList<>();
        // 如果长度小于4
        if (step == 0) {
            return result;
        }
        dfs(result, new ArrayList<>(), s, 0);
        return result;
    }

    private void dfs(List<String> result, List<String> list, String s, int start) {
        if (list.size() == 3) {
            if (isVaild(s, start, s.length())) {
                StringBuilder sb = new StringBuilder();
                for (String str : list) {
                    sb.append(str);
                    sb.append(".");
                }
                sb.append(s.substring(start));
                result.add(sb.toString());
            }
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (!isVaild(s, start, i + 1)) {
                continue;
            }
            list.add(s.substring(start, i + 1));
            dfs(result, list, s, i + 1);
            list.remove(list.size() - 1);
        }
    }

    private boolean isVaild(String str, int left, int right) {
        if (left >= right) {
            return false;
        }
        if (str.charAt(left) == '0' && right-left>1) {
            return false;
        }
        if (right - left > 3) {
            return false;
        }
        Integer value = Integer.valueOf(str.substring(left, right));
        return value >= 0 && value <= 255;
    }
}