面试算法-90-复原 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：

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

解

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        LinkedList<String> path = new LinkedList<>();
        dfs(s, 0, 4, path, result);
        return result;
    }

    public void dfs(String s, int index, int remain, LinkedList<String> path, List<String> result) {
        if (index == s.length() && remain == 0) {
            result.add(String.join(".", path));
        }

        for (int i = index; i < index + 3; i++) {
            if (i >= s.length()) {
                break;
            }

            if (remain * 3 < s.length() - i) {
                break;
            }

            String str = s.substring(index, i + 1);
            if (isSegment(str)) {
                path.add(str);
                dfs(s, i + 1, remain - 1, path, result);
                path.removeLast();
            }
        }
    }

    public boolean isSegment(String str) {
        return Integer.valueOf(str) <= 255 && ("0".equals(str) || str.charAt(0) != '0');
    }
}
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