93.复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和"192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

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

示例 2：

1
2
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

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

for (int j = i; j < i + 3 && j < n; j++)的遍历条件好

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class Solution {
    private   List<String> ans = new ArrayList<>();
    private   List<String> path = new ArrayList<>();
    private   int n;
    // 主要方法，接受一个字符串 s 表示未分隔的 IP 地址，并返回所有可能的有效 IP 地址组合
    public List<String> restoreIpAddresses(String s) {
        int n = s.length();
        this.n=n;
        // 开始深度优先搜索，初始状态为索引 0
        dfs(s, 0);

        return ans;
    }

    // 深度优先搜索方法
    private void dfs(String s, int i) {
        // 终止条件：当到达字符串末尾且路径长度为4时，将路径加入结果中
        if (i == n && path.size() == 4) {
            ans.add(String.join(".", path));
            return;
        }

        // 剪枝条件：当路径长度超过4或剩余字符不足以填充路径时，终止递归
        if (path.size() >= 4 || (n - i) < (4 - path.size())) {
            return;
        }

        // 遍历字符串的每个可能的段落
        for (int j = i; j < i + 3 && j < n; j++) {
            String segment = s.substring(i, j + 1);
            // 检查段落是否为有效的IP段
            if (isValid(segment)) {
                path.add(segment);
                dfs(s, j + 1);
                path.remove(path.size() - 1); // 回溯
            }
        }
    }

    // 检查IP段是否有效
    private boolean isValid(String segment) {
        if (segment.length() > 1 && segment.startsWith("0")) {
            return false; // 以0开头的段必须为单个0
        }
        int num=Integer.parseInt(segment);
      
        return num >= 0 && num <= 255;
    }
}