一、题目描述

题目大意：编写一个函数来验证输入的字符串是否是有效的 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 是无效的。说明: 你可以认为给定的字符串里没有空格或者其他特殊字符。 注意审题：IPv6是允许前导零的, 可能出现非法字符，因此需要特判

二、算法1（分类讨论）

解题思路

  1. 对于此类根据给定规则进行判断合法性的题目，常用的方法就是分类讨论或者状态机。由于本题涉及到的装太比较少，因此可以采用分类讨论的方法解决
  2. 根据 IPv4 和 IPv6 的分隔符可以确定考虑的是 IPv4 地址还是 IPV6 地址，然后分别实现检查IPv4 和 IPv6 地址的函数即可
  3. 检查的内容如下图： 图片说明 图片说明

代码实现（C++）

class Solution {
public:
 string solve(string IP) {
     // 根据标识符确定此IP的类型
     bool isIPv4 = false;
     bool isIPv6 = false;

     for (auto & ch : IP) {
         if(ch == '.') isIPv4 = true;
         if(ch == ':') isIPv6 = true;
     }

     if(isIPv4 == isIPv6) return "Neither";
     else if(isIPv4) return checkIPv4(IP);
     return checkIPv6(IP);
 }

 // 检查IPv4地址的正确性
 string checkIPv4(string& IP) {
     int n = IP.size(), count = 0;
     // 首先确保每个'.'前后都是数字且点的个数必须为3个
     for (int i = 0; i < n; i++) {
         // 检查是否有字母
         if (isalpha(IP[i])) return "Neither";
         if (IP[i] == '.') {
             count++;
             // 位于边界
             if (i == 0 || i == n - 1) return "Neither";

             // 前后有非数字
             if (!isdigit(IP[i - 1]) || !isdigit(IP[i + 1])) return "Neither"; 
         }
         else {
             // 前导零
             if(i + 1 < n && IP[i] == '0' && isdigit(IP[i + 1])) return "Neither";

             // 取出十进制数
             int j = i, digit = 0;    
             while (j < n && isdigit(IP[j]) && digit <= 255) {
                 digit = digit * 10 + (IP[j] - '0');
                 j++;
             }
             if(digit < 0 || digit > 255) return "Neither";
             i = j - 1;
         }
     }
     return count == 3 ? "IPv4" : "Neither";
 }

 // 检查IPv6地址的正确性
 string checkIPv6(string& IP) {
     int n = IP.size(), count = 0;
     // 同样确保每个':'前后都有字母且个数为7个
     for (int i = 0; i < n; i++) {
         if (IP[i] == ':') {
             count++;
             // 位于边界
             if (i == 0 || i == n - 1) return "Neither";
             // 前后都无':'
             if (IP[i - 1] == ':' || IP[i + 1] == ':') return "Neither";
         }
         else {
             // 检查位数和字符串合法性
             int j = i, cnt = 0;
             while(j < n && IP[j] != ':') {
                 cnt++;    // 位数加一
                 if(!isdigit(IP[j]) && tolower(IP[j]) > 'f') return "Neither";
                 j++;
             }
             if (cnt > 4) return "Neither";
             i = j - 1;
         }
     }
     return count == 7 ? "IPv6" : "Neither";
 }
};

时间复杂度：O(n)O(n)，n为字符串的长度，对字符串最多遍历两次，故时间复杂度为线性 空间复杂度：O(1)O(1)，使用常数个中间变量

三、算法2（正则表达式）

解题思路

正则表达式描述了一种字符串匹配的模式。一般使用正则表达式主要是实现下面三个需求：

  1. 检查一个串是否包含某种形式的子串
  2. 将匹配的子串替换
  3. 从某个串中取出符合条件的子串 而我们的任务是验证IP地址，且有限定的形式，因此可以采用正则表达式来检查字符串是否符合规定格式，C++11 提供的正则表达式库操作std::string对象，模式std::regex进行初始化，通过std::regex_match进行匹配，当匹配成功时会返回true，否则返回false

代码实现（C++11）

#include <regex>    //使用regex需要包含此头文件

class Solution {
public:
    string solve(string IP) {
        //定义IPv4的匹配方法
        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])");
        // 定义IPv6的匹配方法
        regex IPv6("(([0-9a-fA-F]{1,4})\\:){7}([0-9a-fA-F]{1,4})");
        // 使用regex_match方法匹配字符串
        if (regex_match(IP, IPv4)) {    // 匹配IPv4
            return "IPv4";
        }
        else if (regex_match(IP, IPv6)) {    // 匹配IPv6
            return "IPv6";
        }
        return "Neither";    // 都没匹配成功
    }
};

时间复杂度：O(n)O(n)，n为字符串长度，时间复杂度取决于std::regex_match的实现，为O(n)O(n) 空间复杂度：O(1)O(1)，使用有限个变量，空间复杂度为O(1)O(1)