LeetCode题练习与总结：验证 IP 地址--468

一、题目描述

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

有效的IPv4地址 是 “x1.x2.x3.x4” 形式的IP地址。其中 0 <= xi <= 255 且 xi 不能包含 前导零。例如: “192.168.1.1” 、 “192.168.1.0” 为有效IPv4地址， “192.168.01.1” 为无效IPv4地址; “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" 和 "2001:db8:85a3:0:0:8A2E:0370:7334" 是有效的 IPv6 地址，而 "2001:0db8:85a3::8A2E:037j:7334" 和 "02001:0db8:85a3:0000:0000:8a2e:0370:7334" 是无效的 IPv6 地址。

示例 1：

输入：queryIP = "172.16.254.1"
输出："IPv4"
解释：有效的 IPv4 地址，返回 "IPv4"

示例 2：

输入：queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
输出："IPv6"
解释：有效的 IPv6 地址，返回 "IPv6"

示例 3：

输入：queryIP = "256.256.256.256"
输出："Neither"
解释：既不是 IPv4 地址，又不是 IPv6 地址

提示：

queryIP 仅由英文字母，数字，字符 '.' 和 ':' 组成。

二、解题思路

首先，我们可以通过检查字符串中是否包含字符 ‘.’ 或 ‘:’ 来判断它是 IPv4 还是 IPv6 地址。
对于 IPv4 地址：
- 使用 ‘.’ 分割字符串，检查分割后的数组长度是否为 4。
- 对于每个分割后的字符串，检查是否在 0 到 255 之间，且没有前导零（除非字符串就是 “0”）。
对于 IPv6 地址：
- 使用 ‘:’ 分割字符串，检查分割后的数组长度是否为 8。
- 对于每个分割后的字符串，检查长度是否在 1 到 4 之间，且只包含十六进制字符。
如果都不满足，则返回 “Neither”。

三、具体代码

class Solution {public String validIPAddress(String queryIP) {if (queryIP.contains(".")) {return validateIPv4(queryIP) ? "IPv4" : "Neither";} else if (queryIP.contains(":")) {return validateIPv6(queryIP) ? "IPv6" : "Neither";} else {return "Neither";}}private boolean validateIPv4(String ip) {String[] parts = ip.split("\\.", -1);if (parts.length != 4) return false;for (String part : parts) {if (!part.matches("0|[1-9][0-9]{0,2}")) return false;if (part.length() > 1 && part.startsWith("0")) return false;if (Integer.parseInt(part) > 255) return false;}return true;}private boolean validateIPv6(String ip) {String[] parts = ip.split(":", -1);if (parts.length != 8) return false;for (String part : parts) {if (!part.matches("[0-9a-fA-F]{1,4}")) return false;}return true;}
}

在这段代码中，我们使用了正则表达式来验证 IPv4 和 IPv6 地址的各个部分。对于 IPv4，我们检查每个部分是否是 0 到 255 之间的数字，且没有前导零（除非部分是 “0”）。对于 IPv6，我们检查每个部分是否只包含 1 到 4 个十六进制字符。

四、时间复杂度和空间复杂度

1. 时间复杂度

validateIPv4 方法：
- split("\\.", -1)：这个操作会遍历整个字符串 queryIP 一次，所以时间复杂度是 O(n)，其中 n 是 queryIP 的长度。
- parts.length != 4：这是一个常数时间操作，时间复杂度是 O(1)。
- 循环遍历 parts 数组：这个循环会执行 4 次（因为有效的 IPv4 地址有 4 个部分），所以时间复杂度是 O(1)。
  - part.matches("0|[1-9][0-9]{0,2}")：这是一个正则表达式匹配操作，时间复杂度取决于正则表达式的复杂度，但由于正则表达式固定且简单，可以认为它是 O(1)。
  - part.startsWith("0")：这是一个常数时间操作，时间复杂度是 O(1)。
  - Integer.parseInt(part) > 255：这是一个常数时间操作，时间复杂度是 O(1)。
- 综合以上，validateIPv4 方法的时间复杂度是 O(n)。
validateIPv6 方法：
- split(":", -1)：这个操作会遍历整个字符串 queryIP 一次，所以时间复杂度是 O(n)，其中 n 是 queryIP 的长度。
- parts.length != 8：这是一个常数时间操作，时间复杂度是 O(1)。
- 循环遍历 parts 数组：这个循环会执行 8 次（因为有效的 IPv6 地址有 8 个部分），所以时间复杂度是 O(1)。
  - part.matches("[0-9a-fA-F]{1,4}")：这是一个正则表达式匹配操作，时间复杂度同样是 O(1)。
- 综合以上，validateIPv6 方法的时间复杂度也是 O(n)。

2. 空间复杂度

validateIPv4 方法：
- parts 数组：这个数组固定有 4 个元素，所以空间复杂度是 O(1)。
validateIPv6 方法：
- parts 数组：这个数组固定有 8 个元素，所以空间复杂度是 O(1)。

综上所述，整体的时间复杂度是 O(n)，空间复杂度是 O(1)。这里的空间复杂度只考虑了额外的空间使用，没有考虑输入字符串 queryIP 本身占用的空间。

五、总结知识点

字符串操作：
- contains(String str): 检查字符串是否包含指定的子字符串。
- split(String regex, int limit): 根据匹配给定的正则表达式来拆分字符串，并限定拆分次数。
正则表达式：
- matches(String regex): 告知这个字符串是否匹配给定的正则表达式。
- 正则表达式的基本用法，如字符类（. 表示任意字符，[0-9] 表示数字，[a-fA-F] 表示十六进制字符）和量词（{0,2} 表示匹配前面的字符 0 到 2 次）。
条件判断：
- if-else 语句：用于根据条件执行不同的代码块。
字符串与整数的转换：
- Integer.parseInt(String s): 将字符串参数解析为带符号的整数。
字符串方法：
- startsWith(String prefix): 检查字符串是否以指定的前缀开始。
数组操作：
- 数组的声明和使用。
- 使用增强型 for 循环遍历数组。
方法重载：
- 在同一个类中定义了两个同名的 validateIPvX 方法，但参数类型不同，这是方法重载的一个例子。
返回值：
- 方法返回布尔值以表示条件是否满足。
- 方法返回字符串以表示 IP 地址的类型。
面向对象编程：
- 使用私有方法 validateIPv4 和 validateIPv6 来封装验证逻辑，体现了封装的原则。