题解 | #验证IP地址#

题目描述
编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址
IPv4 地址由十进制数和点来表示，每个地址包含4个十进制数，其范围为 0 - 255，用(".")分割。比如，172.16.254.1；
同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。
IPv6 地址由8组16进制的数字来表示，每组表示 16 比特。这些组数字通过 (":")分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以， 2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址 (即，忽略 0 开头，忽略大小写)。
然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。比如， 2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。
同时，在 IPv6 地址中，多余的 0 也是不被允许的。比如， 02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。
说明: 你可以认为给定的字符串里没有空格或者其他特殊字符。

方法一：暴力求解--分割字符串直接比较

求解思路
本题目中要对IP字符串进行分割，我们可以协议个分割函数，遍历IP字符串，遇到.或者:将其分开存储在一个vector中，遍历vector，判断其中每个字符串是否符合题目描述中所给的要求，然后对结果进行输出

图片说明

解题代码

class Solution {
public:
    vector<string> split(string s, string spliter)
    {   //将字符串从.或者:分割开
        vector<string> myres; // 声明vector存储结果
        int i;
        while ((i = s.find(spliter)) && i != s.npos) 
        {   //遍历字符串查找spliter
            myres.push_back(s.substr(0, i)); // 将分割的部分加入vector中
            s = s.substr(i + 1);
        }
        myres.push_back(s);
        return myres;
    }
    bool isIPv4 (string IP) // 判断是否为IPv4类型
    {
        vector<string> s = split(IP, ".");
        if (s.size() != 4) // IPv4必定为4组
            return false;
        for (int i = 0; i < s.size(); i++) 
        {
            if (s[i].size() == 0) // 不可缺省，有一个分割为零，说明两个点相连
                return false;
            //比较数字位数及不为零时不能有前缀零
            if (s[i].size() < 0 || s[i].size() > 3 || (s[i][0]=='0' && s[i].size() != 1))  
                return false;
            for (int j = 0; j < s[i].size(); j++) // 遍历每个分割字符串，必须为数字
                if (!isdigit(s[i][j])) 
                    return false;
            int num = stoi(s[i]); // 转化为数字比较，0-255之间
            if (num < 0 || num > 255) 
                return false;
        }
        return true;
    }
    bool isIPv6 (string IP) // 判断是否为IPv6类型
    {
        vector<string> s = split(IP, ":");
        if (s.size() != 8) // IPv6必定为8组
            return false;
        for (int i = 0; i < s.size(); i++) 
        { 
            if (s[i].size() == 0 || s[i].size() > 4) // 每个分割不能缺省，不能超过4位
                return false; 
            for (int j = 0; j < s[i].size(); j++)
            {
                //不能出现a-fA-F以外的大小写字符
                if (!(isdigit(s[i][j]) || (s[i][j] >= 'a' && s[i][j] <= 'f') || (s[i][j] >= 'A' && s[i][j] <= 'F')))
                    return false;
            }
        }
        return true;
    }
    string solve(string IP) 
    {
        if(IP.size() == 0)
            return "Neither";
        if(isIPv4(IP)) // 先判断是否为IPv4
            return "IPv4";
        else if(isIPv6(IP)) // 再判断是否为IPv6
            return "IPv6";
        return "Neither";
    }
};

复杂度分析
时间复杂度：对于分割字符串需要遍历整个字符串，因此时间复杂度为 $O(N)$ ，N为字符串的长度
空间复杂度：存储分割字符串的临时空间为常数4或者8，因此空间复杂度为 $O(1)$

方法二：优化解法--正则表达式求解

求解思路
对于本题目，我们可以采用正则表达式来进行求解，对于IPV4，我们限制其每一组的数字为0-255，没有前缀0，并且四组齐全。对于IPV6，我们限制其每一位为0-9或a-f或A-F，并且有8组。然后根据以上规则，我们对本题目进行求解，即可得到答案。

图片说明

解题代码

#include <regex> // include正则表达式的库
class Solution {
public:
    string solve(string IP) {
        //正则表达式限制0-255 且没有前缀0 四组齐全
        regex ipv4("(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])");
        //正则表达式限制出现8组，0-9a-fA-F的数，个数必须是1-4个
        regex ipv6("([0-9a-fA-F]{1,4}\\:){7}[0-9a-fA-F]{1,4}");
        if (regex_match(IP, ipv4)) // 调用ipv4正则匹配函数
            return "IPv4"; // 若是IPv4，则返回IPv4
        else if (regex_match(IP, ipv6)) // 调用ipv6正则匹配函数
            return "IPv6"; // 若是IPv6，则返回IPv6
        else return "Neither";
    }
};

复杂度分析
时间复杂度：需要遍历整个字符串，因此时间复杂度为 $O(N)$ ，N为字符串的长度
空间复杂度：没有引入额外的地址空间，因此空间复杂度为 $O(1)$