LeetCode 468. 验证IP地址
目录
题目描述
题意分析
给定字符串，判断它是合法 IPv4（返回
"IPv4"）、合法 IPv6（返回"IPv6"），还是都不是（返回"Neither"）。本题没有算法难度，全部难点在于把规则逐条列清、一条不漏，面试时最好先当着面试官的面把规则复述一遍再动手。IPv4 的合法规则：
- 恰好 4 段，用
.分隔，段与段之间、首尾都不能出现空段（"1.1.1.1."尾部多一个点即非法）。- 每段只含十进制数字，不允许正负号、空格或其他字符。
- 每段数值在 0 到 255 之间。
- 不允许前导零：
"01.1.1.1"无效，"0.1.1.1"有效——即长度大于 1 的段不能以0开头。IPv6 的合法规则：
- 恰好 8 段，用
:分隔，同样不允许空段，因此"::"这种现实中合法的缩写在本题中无效。- 每段长度 1 到 4，字符只能是十六进制字符
0-9、a-f、A-F，大小写均可。- 允许前导零（与 IPv4 相反），但整段长度仍不能超过 4：
"02001:..."因为长度 5 而无效。边界信号：字符串长度至多 50，可能不含任何分隔符（如纯数字
"1e1"），也可能同时混入两种分隔符，这些都应返回"Neither"。
解法：分段后逐条校验规则
核心思路
问题关键：这不是数值转换题，而是格式校验题。IPv4 要同时满足段数、字符、数值范围和前导零规则；IPv6 要满足段数、段长和十六进制字符规则，漏掉任意一项都会误判。
为什么选分段校验：两类地址的分隔符不同，先按
.或:分流，再让两个辅助函数各自负责一套规则，比大正则更容易说明和验证。切分必须保留空段，否则尾随分隔符会被漏掉。不变量与正确性：进入段循环前已经确认段数正确；每轮结束后，当前段之前的所有段都满足该地址类型的全部规则。遇到任一违规立即返回
false，循环完成说明每个必要条件都成立，因此地址合法。
解题步骤
- 字符串含
.时只尝试 IPv4；否则含:时只尝试 IPv6；都不含则返回"Neither"。- IPv4 按
.切成 4 段，并保留首尾及连续分隔符产生的空段。- 每个 IPv4 段长度必须为 1～3；多位数不能以
0开头；逐字符确认是 ASCII 数字并累加，值不能超过 255。- IPv6 按
:切成 8 段；每段长度必须为 1～4，字符只能是0-9、a-f、A-F。- 任一检查失败就返回
"Neither"，全部通过才返回对应类型。
代码实现
class Solution {
public String validIPAddress(String queryIP) {
if (queryIP.indexOf('.') >= 0) {
return isIPv4(queryIP) ? "IPv4" : "Neither";
}
if (queryIP.indexOf(':') >= 0) {
return isIPv6(queryIP) ? "IPv6" : "Neither";
}
return "Neither";
}
private boolean isIPv4(String ip) {
String[] parts = ip.split("\\.", -1);
if (parts.length != 4) {
return false;
}
for (String part : parts) {
if (part.isEmpty() || part.length() > 3
|| (part.length() > 1 && part.charAt(0) == '0')) {
return false;
}
int value = 0;
for (int i = 0; i < part.length(); i++) {
char ch = part.charAt(i);
if (ch < '0' || ch > '9') {
return false;
}
value = value * 10 + ch - '0';
}
if (value > 255) {
return false;
}
}
return true;
}
private boolean isIPv6(String ip) {
String[] parts = ip.split(":", -1);
if (parts.length != 8) {
return false;
}
for (String part : parts) {
if (part.isEmpty() || part.length() > 4) {
return false;
}
for (int i = 0; i < part.length(); i++) {
if (!isHexDigit(part.charAt(i))) {
return false;
}
}
}
return true;
}
private boolean isHexDigit(char ch) {
return ch >= '0' && ch <= '9'
|| ch >= 'a' && ch <= 'f'
|| ch >= 'A' && ch <= 'F';
}
}
func validIPAddress(queryIP string) string {
if strings.Contains(queryIP, ".") {
if isIPv4(queryIP) {
return "IPv4"
}
return "Neither"
}
if strings.Contains(queryIP, ":") {
if isIPv6(queryIP) {
return "IPv6"
}
return "Neither"
}
return "Neither"
}
func isIPv4(ip string) bool {
parts := strings.Split(ip, ".")
if len(parts) != 4 {
return false
}
for _, part := range parts {
if len(part) == 0 || len(part) > 3 || len(part) > 1 && part[0] == '0' {
return false
}
value := 0
for i := 0; i < len(part); i++ {
if part[i] < '0' || part[i] > '9' {
return false
}
value = value*10 + int(part[i]-'0')
}
if value > 255 {
return false
}
}
return true
}
func isIPv6(ip string) bool {
parts := strings.Split(ip, ":")
if len(parts) != 8 {
return false
}
for _, part := range parts {
if len(part) == 0 || len(part) > 4 {
return false
}
for i := 0; i < len(part); i++ {
if !isHexDigit(part[i]) {
return false
}
}
}
return true
}
func isHexDigit(ch byte) bool {
return ch >= '0' && ch <= '9' || ch >= 'a' && ch <= 'f' || ch >= 'A' && ch <= 'F'
}
复杂度分析
- 时间复杂度：$O(n)$，切分和校验都只线性扫描字符串。
- 空间复杂度：$O(n)$，切分出的段占用线性空间；手动扫描段边界可降为 $O(1)$，但会增加实现细节。
关键点总结
- 校验顺序固定为「段数 → 段长 → 字符 → 额外规则」，便于口述，也便于查漏。
- Java
split要传-1保留尾部空段；"1.1.1.1."必须判错。- IPv4 的前导零与数值范围是两条独立规则；IPv6 允许前导零，但不接受
::缩写。- 手动检查 ASCII 字符比
parseInt更合适，可直接拒绝正负号等非数字字符。
易错点总结
- Java 直接用
split("\\.")会丢掉尾部空段，可能把"1.1.1.1."误判为 IPv4。- 只判断数值会放过
"01.1.1.1"；多位 IPv4 段必须单独检查前导零。- 用
Integer.parseInt会接受+1，所以"+1.2.3.4"仍应逐字符判错。- IPv6 不能把现实中的压缩写法直接套进题目；
"2001:db8::1"含空段，本题返回"Neither"。- 十六进制字符要同时支持大小写；
8A2E合法，8G2E非法。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 93. 复原 IP 地址 | 中等 | 反向问题：用回溯枚举所有合法 IPv4 切分 |
| 165. 比较版本号 | 中等 | 同为按 . 分段解析，但比较数值而非校验 |
| 393. UTF-8 编码验证 | 中等 | 校验对象换成字节的位模式，规则驱动同款思路 |
| 65. 有效数字 | 困难 | 规则更多且相互嵌套，需要状态机组织校验 |