复原IP地址 | LeetCode-93 | 回溯算法 | 切割

发表于 更新于 分类于 ， ， 阅读次数： 阅读次数： Waline： 本文字数： 2.9k 阅读时长 ≈ 5 分钟

回溯算法练习题

LeetCode链接：93. 复原 IP 地址

1.题目描述

有效 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"]

提示：

  • 1 <= s.length <= 20
  • s 仅由数字组成

2.题解

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    // 定义一个列表 result，用于存储最终生成的所有合法的 IP 地址
    List<String> result = new ArrayList<>();

    // 主方法 restoreIpAddresses，输入一个字符串 s，返回所有可能的合法 IP 地址
    public List<String> restoreIpAddresses(String s) {
        // 如果字符串的长度不在有效范围内（4 到 12），直接返回空结果
        if (s.length() < 4 || s.length() > 12) return result;
        // 使用回溯算法生成所有可能的 IP 地址
        backtracking(s, new StringBuilder(), 0, 0);
        // 返回结果列表
        return result;
    }

    // 回溯算法方法 backtracking，构建有效的 IP 地址
    public void backtracking(String s, StringBuilder sb, int start, int level) {
        int len = s.length();

        // 当分割为 3 段时，处理剩下的最后一段
        if (level == 3) {
            // 如果剩余部分的长度超过 3 或 start 越界，则直接返回
            if (len - (start + 1) > 3 || start >= len) return;
            // 提取最后一段的字符串
            String sub = s.substring(start, len);
            // 检查这段字符串是否合法，如果合法则加入到结果中
            if (isValid(sub)) {
                sb.append(sub);  // 添加最后一段
                result.add(sb.toString());  // 将完整的 IP 地址添加到结果列表中
            }
            return;
        }

        // 从 start 开始，最多取 3 位字符
        for (int i = start; i < len && i - start < 3; i++) {
            // 提取从 start 到 i 的子字符串
            String sub = s.substring(start, i + 1);
            // 如果当前段不合法，直接返回
            if (!isValid(sub)) return;
            // 添加当前段到 StringBuilder，并添加一个 '.' 分隔符
            sb.append(sub).append(".");
            // 递归处理剩余的字符串
            backtracking(s, sb, i + 1, level + 1);
            // 回溯：删除刚才添加的字符，以便尝试其他组合
            sb.delete(start + level, sb.length());
        }
    }

    // 辅助方法 isValid，用于判断一个字符串是否为合法的 IP 地址段
    public boolean isValid(String s) {
        int len = s.length();
        
        // 如果字符串长度大于 1 且以 '0' 开头，则该段不合法（IP 段不能以 '0' 开头）
        if (len > 1 && s.charAt(0) == '0') return false;

        // 检查字符串中的字符是否全为数字
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c < '0' || c > '9') return false;
        }

        // 将字符串转换为整数，并检查是否在 0 到 255 的范围内
        int num = Integer.parseInt(s);
        return num >=0 && num <=255;
    }
}

3.练习

给定一个字符串 queryIP。如果是有效的 IPv4 地址，返回 "IPv4"；如果是有效的 IPv6 地址，返回 "IPv6"；如果不是上述类型的 IP 地址，返回 "Neither"。

有效的 IPv4 地址: 是x1.x2.x3.x4形式的 IP 地址，其中0 <= xi <= 255，且xi不能包含前导零。

  • 例如："192.168.1.1" 是有效的 IPv4 地址。
  • "192.168.1.01"、"192.168.1.00"、"192.168@1.1" 是无效的 IPv4 地址。

有效的 IPv6 地址: 是x1:x2:x3:x4:x5:x6:x7:x8形式的 IP 地址，其中1<=xi.length<=4，xi是一个十六进制字符串，可以包含数字、小写字母（从 ‘a’到 ‘f’）和大写字母（从 ‘A’到 ‘F’），在xi中允许前导零。

  • 例如："2001:0db8:85a3:0000:0000:8a2e:0370:7334" 是有效的 IPv6 地址。
  • "2001:db8:85a3::8a2e:0370:7334" 和 "02001:0db8:85a3:0000:0000:8a2e:0370:7334" 是无效的 IPv6 地址。
-------------本文结束感谢您的阅读-------------