LeetCode93-复原IP地址

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/restore-ip-addresses/

中文链接：https://leetcode-cn.com/problems/restore-ip-addresses/

题目详述

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

示例:

1
2
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

题目详解

DFS。

  • 当长度小于 4 时，不可能构造出一个合理的 IP，可以直接返回。
  • 每次尝试构造出被 . 分割的一部分，这一部分必须满足不以 0 开头且小于等于 255.
  • 递归的结束条件是四部分被构造出，并且刚好整个字符串被分割，不能有剩余。
  • 当构造的数量大于 4 时，没必要再继续搜索，不可能得到合理的 IP。
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
public class LeetCode_00093 {

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() < 4) {
            return res;
        }
        dfs(s, res, new StringBuilder(), 0, 0);
        return res;
    }

    private void dfs(String s, List<String> res, StringBuilder ip, int index, int cnt) {
        if (cnt > 4) {
            return;
        }
        if (cnt == 4 && index == s.length()) {
            res.add(ip.toString());
            return;
        }
        for (int i = 1; i < 4; ++i) {
            int end = index + i;
            if (end > s.length()) {
                break;
            }
            String sub = s.substring(index, end);
            if ((sub.startsWith("0") && sub.length() > 1) || Integer.parseInt(sub) > 255) {
                break;
            }
            if (cnt < 3) {
                sub += ".";
            }
            ip.append(sub);
            dfs(s, res, ip, end, cnt + 1);
            ip.delete(ip.length() - sub.length(), ip.length());
        }
    }
}