Leetcode - 93. 复原IP地址

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ret = new ArrayList<>();
        
        // 将字符串转成整数数组，方便操作
        int[] nums = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            nums[i] = s.charAt(i) - '0';
        }
        
        // 从nums[0]处开始解析ip地址
        dfs(nums, 0, new int[4], 0, ret);
        
        return ret;
    }

    // 从nums[begin]处开始解析ip地址
    private static void dfs(int[] nums, int begin, int[] ip, int idx, List<String> ret) {

        // 如果剩余的未解析的部分过长或过短，则解析失败
        // 比如ip地址已经解析了前2段，但nums的剩余部分长度大于6或小于2，此时解析失败
        if (nums.length - begin > (4 - idx) * 3 || nums.length - begin < 4 - idx) {
            return;
        }

        // 如果已经解析出了4部分的ip地址，则将结果保存起来
        if (idx == 4) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 3; i++){
                sb.append(ip[i]);
                sb.append('.');
            }
            sb.append(ip[3]);
            ret.add(sb.toString());
            return;
        }

        // ================================= 否则开始尝试解析 =================================

        // 临时变量
        int sum = nums[begin];
        
        // 首先，当前数肯定可以作为ip地址单独的一段，因此先尝试单独解析
        ip[idx] = sum;
        dfs(nums, begin + 1, ip, idx + 1, ret);

        // 然后再尝试用当前数和下一个数作为ip地址的一段来解析，前提是当前数不为0
        if (begin + 1 == nums.length || (sum = sum * 10 + nums[begin + 1]) < 10) {
            return;
        }
        ip[idx] = sum;
        dfs(nums, begin + 2, ip, idx + 1, ret);

        // 然后再尝试用当前数和后面两个数作为ip地址的一段来解析，前提是三者组成的数小于256
        if (begin + 2 == nums.length || (sum = sum * 10 + nums[begin + 2]) >= 256) {
            return;
        }
        ip[idx] = sum;
        dfs(nums, begin + 3, ip, idx + 1, ret);
    }
}