【算法-Java】给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

一、示例

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

二、说明

1. 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
2. 例如：“0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效的 IP 地址。

三、Demo

public class Solution {
    public static void main(String[] args) {
        String s = "101023";
        System.out.println(Solution.restoreIpAddresses(s));
    }

    // cur: 当前答案,以List<String>的形式,最后再join成String形式,例如[[255],[255],[111],[35]] -> 255.255.111.35
    // pos: 当前扫描到的s的位置
    // ans: 最终答案
    public static void backtracking(String s, int pos, List<String> cur,  List<String> ans) {
        // [[255],[255],[111],[35]] List<String>长度 = 4
        if (cur.size() >= 4) {
            if (pos == s.length()) {
                ans.add(String.join(".", cur));
            }
            return;
        }
        // 分割得到ip地址的一段后,下一段只能在长度1-3范围内选择
        for (int i = 1; i <= 3; i++) {
            if (pos+i > s.length()) {
                break;
            }
            String segment = s.substring(pos, pos+i);
            // 剪枝条件：不能以0开头，不能大于255
            if (segment.startsWith("0") && segment.length() > 1 || (i == 3 && Integer.parseInt(segment) > 255)) {
                continue;
            }
            cur.add(segment);
            // 注意此处传的参数
            backtracking(s, pos+i, cur, ans);
            cur.remove(cur.size()-1);
        }
    }
    public static List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        backtracking(s, 0, new ArrayList<>(), ans);
        return ans;
    }
}