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:

输入:queryIP = "172.16.0.1"
输出:"IPv4"
解释:四段均为无前导零的 0..255 十进制整数。

输入:queryIP = "2001:db8:0:0:1:0:0:1"
输出:"IPv6"
解释:地址恰好有八个合法十六进制字段。

IPv4 前导零非法:

输入:queryIP = "01.2.3.4"
输出:"Neither"
解释:第一段 01 含有不允许的前导零。

分隔符、字符集和数值范围分别校验

IPv4 和 IPv6 的规则不同,先按出现的分隔符选择对应校验器。IPv4 必须得到恰好四个非空十进制段,单段长度超过 1 时不能以 0 开头,并在逐位构造时检查不超过 255;IPv6 必须得到恰好八个非空字段,每个字段长度为 1 到 4,且每个字符都属于十六进制字符集。

不把字符串直接交给数值转换函数,可以同时控制空段、前导零、非法字符和字段数量,避免转换函数对边界格式作出宽松解释。

C++ 实现

class Solution {
    bool isIPv4(const std::string& s) {
        int parts = 0;
        int begin = 0;
        for (int i = 0; i <= static_cast<int>(s.size()); ++i) {
            if (i < static_cast<int>(s.size()) && s[i] != '.') {
                if (!std::isdigit(static_cast<unsigned char>(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<unsigned char>(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<int>(s.size()); ++i) {
            if (i < static_cast<int>(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)。