题解 | #验证IP地址#

nc113. 验证IP地址

题意

给你一个字符串，判定是不是合法的IPV4,IPV6的地址，或者都不是。

1. 直接模拟

根据题意注意下实现细节即可。

IPV4字符串有以下判断要点：

被点切割后的数组长度必须为4
数组中每个元素都是数字，大小范围是0~255之间
（这里wa了一次）不能出现前导0！！！

IPV6字符串中有以下判断要点：

被冒号切割后的数组长度必须为8
数组中每个元素都是1-4位的十六进制字符串，允许大小写混合
可以出现前导0！！！！

如果本题用C++实现，还有一个难点就是split函数，在标准库中不存在split，所以我们要手写一个简易的split。手写split是一个典型的快慢指针问题， split的实现思路：

定义两个指针，start和end
从头开始遍历字符串，如果遇到了分割符，将start到end之间的字符串加入数组，并重置start和end为分隔符的下一位置，否则end++；
字符串遍历完如果还剩一段，即start未指向字符串末尾，则把最后一块加入数组。

split的过程如下图所示，以"192.168.1.123"为例：

图片说明

end一起右移，遇到点，则记录start到end之间的子串加入res，此时res=["192"]
加入后，start=end+1, 开始遍历下一块。并且end继续右移。
end又遇到了一个点，重复步骤1. 直到end走完。此时res= ["192", "168", "1"]
while循环退出，发现start未指向字符串最尾端，说明还剩一段，加入到res, 此时执行res.push_back("123").

class Solution {
public:
    // 自己写的split函数
    vector<string> split(string s, char ch) {
        int start=0, end=0;
        vector<string> res;

        while (end < s.length()) {
            // 快指针遇到分隔符，记录下当前块内容，然后两个指针同时从下一块开始
            if (s[end] == ch) {
                res.push_back(s.substr(start, end-start));
                start = end+1;
            }

            // end指针一直右移
            end++;
        }

        // 对最后一块的处理
        if (start < s.length())
            res.push_back(s.substr(start, end-start));
        return res;
    }

    bool isIPV4(string &ip) {
        vector<string> strs = split(ip, '.');
        // 不是4个元素，是错误答案
        if (strs.size() != 4) return false;

        for (auto str : strs) {
            int n = 0; // 记录每一块的数字

            // 不能有前导0
            if (str.size() > 0 && str[0] == '0')
                return false;
            for (auto c : str) {
                // 出现了非数字，直接返回错误
                if (!isdigit(c)) return false;
                n = n*10 + (c-'0');
            }

            // 判断是不是在0-255之间，确保n是正数了
            if (n > 255) return false;
        }

        return true;
    }

    bool isIPV6(string &ip) {
        vector<string> strs = split(ip, ':');
        // 判断长度是否为8
        if (strs.size() != 8) return false;

        for (auto str : strs) {
            int n = str.size();
            // 每段长度在1-4之间
            if (n < 1 || n > 4) return false;

            for (auto c : str) {
                // 每一段都由16进制字符组成，大小写任意
                if (!(isdigit(c) || (c >= 'A' && c <= 'F') || (c >= 'a' || c <= 'f'))) 
                    return false;
            }
        }
        return true;
    }



    string solve(string IP) {
        if (isIPV4(IP)) return "IPv4";
        else if (isIPV6(IP)) return "IPv6";
        return "Neither";
    }
};

时间复杂度：对于长度为n的字符串IP，先进行了split切分，再遍历，计算量均与n成正比，所以是 $O(n)$ .
空间复杂度：用到了切分后的数组res，res的长度也与n成正比，所以空间也是 $O(n)$ .

2. 用正则表达式

IPv4的正则表达式：

每一段里面是0~255的数字，分别讨论2开头（2[0-4]\d|25[0-5])，1开头(1\d\d)，两位数([1-9]\d)，1位数(\d)的情况
每一段后面加一个点，构成一个整体，重复3次
后面再加上那一段

IPv6的正则表达式：

每一段都是1-4位的16进制字符，用[\da-fA-F]表示
加上冒号重复七遍，再加上最后一段

因为cpp中没有正则库，故方法二换用Java实现。

import java.util.*;
import java.util.regex.Pattern;

public class Solution {
    /**
     * 验证IP地址
     * @param IP string字符串 一个IP地址字符串
     * @return string字符串
     */
    public String solve (String IP) {
        String ipv4 = "^((2[0-4]\\d|25[0-5]|1\\d\\d|[1-9]\\d|\\d)\\.){3}(2[0-4]\\d|25[0-5]|1\\d\\d|[1-9]\\d|\\d)$";
        String ipv6 = "^(([\\da-fA-F]{1,4}):){7}([\\da-fA-F]{1,4})$";
        if (Pattern.matches(ipv4, IP)) return "IPv4";
        else if (Pattern.matches(ipv6, IP)) return "IPv6";
        return "Neither";
    }
}

时间复杂度：正则匹配的时间复杂度也是 $O(n)$ ，因为可以认为是一个自动机，在长度为n的串上进行转移。但是常数远大于方法一
空间复杂度： $O(1)$ .