0468. Validate IP Address
=========================
题目信息
--------
:题号: 0468
:难度: Medium
:主题: IPv4、IPv6、分隔字段、严格格式校验
:原题: `LeetCode 0468 `_
:重点: IPv4 恰好四个十进制段且无前导零、IPv6 恰好八个十六进制段、不支持压缩写法、非法时返回 ``Neither``
题目重述
--------
给定字符串 ``queryIP``,判断它是否是合法 IPv4 地址、合法 IPv6 地址,或两者都不是,并分别返回 ``"IPv4"``、``"IPv6"`` 或 ``"Neither"``。
IPv4 必须由四个用句点分隔的十进制段组成。每段只能含数字,数值位于 ``0..255``;除单独的 ``0`` 外不能有前导零,也不能有正负号或空段。
IPv6 必须由八个用冒号分隔的字段组成。每字段长度为 1 至 4,只能使用十六进制字符 ``0..9``、``a..f``、``A..F``;允许前导零,但不接受 ``::`` 等省略写法,也不能有空字段。输入长度位于 ``[1, 20]``,不允许额外空格。
自建示例
--------
合法 IPv4 与 IPv6:
.. code-block:: text
输入:queryIP = "172.16.0.1"
输出:"IPv4"
解释:四段均为无前导零的 0..255 十进制整数。
输入:queryIP = "2001:db8:0:0:1:0:0:1"
输出:"IPv6"
解释:地址恰好有八个合法十六进制字段。
IPv4 前导零非法:
.. code-block:: text
输入:queryIP = "01.2.3.4"
输出:"Neither"
解释:第一段 01 含有不允许的前导零。
分隔符、字符集和数值范围分别校验
----------------------------------
IPv4 和 IPv6 的规则不同,先按出现的分隔符选择对应校验器。IPv4 必须得到恰好四个非空十进制段,单段长度超过 1 时不能以 0 开头,并在逐位构造时检查不超过 255;IPv6 必须得到恰好八个非空字段,每个字段长度为 1 到 4,且每个字符都属于十六进制字符集。
不把字符串直接交给数值转换函数,可以同时控制空段、前导零、非法字符和字段数量,避免转换函数对边界格式作出宽松解释。
C++ 实现
--------
.. code-block:: cpp
class Solution {
bool isIPv4(const std::string& s) {
int parts = 0;
int begin = 0;
for (int i = 0; i <= static_cast(s.size()); ++i) {
if (i < static_cast(s.size()) && s[i] != '.') {
if (!std::isdigit(static_cast(s[i]))) {
return false;
}
continue;
}
if (i == begin || ++parts > 4) return false;
if (i - begin > 1 && s[begin] == '0') return false;
if (i - begin > 3) return false;
int value = 0;
for (int j = begin; j < i; ++j) {
value = value * 10 + (s[j] - '0');
}
if (value > 255) return false;
begin = i + 1;
}
return parts == 4;
}
bool isHex(char c) {
return std::isdigit(static_cast(c)) ||
(c >= 'a' && c <= 'f') ||
(c >= 'A' && c <= 'F');
}
bool isIPv6(const std::string& s) {
int fields = 0;
int begin = 0;
for (int i = 0; i <= static_cast(s.size()); ++i) {
if (i < static_cast(s.size()) && s[i] != ':') {
if (!isHex(s[i])) return false;
continue;
}
if (i == begin || i - begin > 4 || ++fields > 8) {
return false;
}
begin = i + 1;
}
return fields == 8;
}
public:
std::string validIPAddress(std::string queryIP) {
if (queryIP.find('.') != std::string::npos) {
return isIPv4(queryIP) ? "IPv4" : "Neither";
}
if (queryIP.find(':') != std::string::npos) {
return isIPv6(queryIP) ? "IPv6" : "Neither";
}
return "Neither";
}
};
代码分析
--------
IPv4 的循环在字符串末尾额外处理最后一段,因此尾部句点会形成空段并被拒绝;IPv6 同理拒绝 ``::`` 和首尾冒号。每个字符只扫描常数次,时间复杂度为 ``O(|queryIP|)``,额外空间复杂度为 ``O(1)``。