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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        // 算法：递归回溯

        // 处理特殊情况：
        ArrayList<String> result = new ArrayList<>();
        if (s.length() < 4) {
            return result;
        }
        ArrayList<Integer> nums = new ArrayList<>();
        result = process(s, 0, nums);
        return result;
    }

    public ArrayList<String> process (String s, int i, ArrayList<Integer> nums) {
        int len = s.length();
        ArrayList<String> result = new ArrayList<>();
        // 递归出口
        if (nums.size() == 4 && i == len) {
            StringJoiner sj = new StringJoiner(".");
            for (Integer num : nums) {
                if (num >= 0 && num <= 255) {
                    sj.add(num.toString());
                } else {
                    // 划分错误
                    return null;
                }
            }
            result.add(sj.toString());
            return result;
        } else if (nums.size() == 4 && i < len) {
            // 划分错误
            return null;
        } else if (nums.size() < 4 && i == len) {
            // 划分错误
            return null;
        }

        // 递归分支 - 最多三种情况
        // 这里写的不太好，判断的逻辑全是“补丁”，但答案确实是对的
        for (int j = 1; j <= 3; j++) {
            if (i + j > len) {
                // 下标越界了，不必再往后划分了
                break;
            }
            String sub = s.substring(i, i + j);
            if (sub.length() > 1 && sub.startsWith("0")) {
                // 以0开头的多位数不合法，不必再往后划分了
                break;
            }
            int subNum = Integer.parseInt(sub);
            if (subNum > 255) {
                // 当前数超过255不合法，不必再往后划分了
                break;
            }
            nums.add(subNum);
            ArrayList<String> add = process(s, i + j, nums);
            if (add != null) {
                result.addAll(add);
            }
            // 注意恢复现场
            nums.remove(nums.size() - 1);
        }

        return result;
    }
}