描述

题目描述

给定我们一个字符串，要我们去确定这个字符串是不是符合$IPv4IPv4$或者$IPv6IPv6$, 如果两者都不是的话, 就是$NeitherNeither$

$IPv4\mathrm{的}\mathrm{条}\mathrm{件}IPv4的条件$

1. 中间不可以无数
2. 没有前缀0
3. 值域不可以超过0~255
4. 纯数字
5. 一共四位

$IPv6\mathrm{的}\mathrm{条}\mathrm{件}IPv6的条件$

1. 一共八位
2. 中间每一个长度为0~4
3. 每一位要么是数字或者'a'到'f'或者'A'到'F'

题解

解法一: 因为本题数据特殊会WA

实现思路

为了避免重复造轮子, 我们可以直接调用已经封装好的Python库

这里埋下一个坑, 后序讲

代码实现

from ipaddress import IPv4Address, IPv6Address, ip_address


class Solution:
    def solve(self, IP: str) -> str:
        try:
            if type(ip_address(IP)) is IPv6Address:
                tmp = IP.split(':')
                for i in tmp:
                    if i == "00" or i == "000" or i == "0000" or len(i) == 0:
#                         如果是多的零或者是空着的都不可以
                        return "Neither"
                return "IPv6"
            elif type(ip_address(IP)) is IPv4Address:
                tmp = IP.split('.')
                for i in tmp:
                    if len(i) != 1 and i[0] == '0':
#                         不可以有多余的前导零
                        return "Neither"
                return "IPv4"
        except ValueError:
            return "Neither"
        except IndexError:
            return "Neither"
        # 直接调用库函数判断

时空复杂度分析

时间复杂度: $O(1)O(1)$

理由如下: 因为我们这里的字符串长度最多才是$5050$, 这就是一个常数级别的, 可以理解为$O(1)O(1)$

空间复杂度: $O(1)O(1)$

理由如下: 未引入额外空间

坑点所在

我们的这个类使用的都是引用POSIX-兼容的inet-addr()解析地址, 如果地址有前导零就会有问题, 这里我们在倒数第二组样例会出问题, 所以我们还是要老实的模拟一下做出这道题目, 这里前导零就是类似于这样的数据

"172.016.254.1"

解法二:

实现思路

其实这个题目的本质就是一个大模拟, 根据上面列出来的几种情况模拟一下就可以了

然后这个题目数据上还有一个坑点所在, 就是我们要考虑, 他最后可能会多出来一个$\mathrm{.}\mathrm{或}\mathrm{者}:.或者:$, 所以我们要特判一下最后一位是不是$\mathrm{.}\mathrm{或}\mathrm{者}:.或者:$, 如果是的话直接返回$NeitherNeither$

代码实现

class Solution {
    vector<string> res;

   public:
    bool checkIPV4() {
        if (res.size() != 4) return false;
        // 如果不是4位直接pass
        for (auto &it : res) {
            if (it.size() == 0) return false;
            // 如果中间某一位长度为0, 直接返回false
            if (it.size() < 0 or it.size() >= 4 or
                (it[0] == '0' and it.size() != 1))
                return false;
            // 如果位数不对，或者首位前缀零
            if (stoi(it) < 0 or stoi(it) > 255) return false;
            // 他的值不可以超过这个范围
            for (auto &it1 : it)
                if (!isdigit(it1)) return false;
            // 不是数字的不可以
        }
        return true;
    }
    bool checkIPV6() {
        if (res.size() != 8) return false;
        // 不是八位直接pass
        for (auto &it : res) {
            if (it.size() == 0 or it.size() > 4) return false;
            // 每一位的长度
            for (auto &it1 : it)
                if (!(isdigit(it1) or (it1 >= 'a' and it1 <= 'f') or
                      (it1 >= 'A' and it1 <= 'F')))
                    return false;
            // 每一个位置的取值
        }
        return true;
    }
    string solve(string IP) {
        if (IP.back() == '.' || IP.back() == ':') return "Neither";
        string tmp = "";
        for (auto &it : IP) {
            if (it == '.' or it == ':') {
                res.emplace_back(tmp);
                tmp = "";
                continue;
            }
            tmp += it;
        }
        if (tmp != "") res.emplace_back(tmp);
        // 把我们的IP地址以：或者.来分割开来
        if (res.size() == 4 and checkIPV4()) return "IPv4";
        if (res.size() == 8 and checkIPV6()) return "IPv6";
        return "Neither";
    }
};

时空复杂度分析

时间复杂度: $O(1)O(1)$

理由如下: 因为我们这里的字符串长度最多才是$5050$, 这就是一个常数级别的, 可以理解为$O(1)O(1)$

空间复杂度: $O(1)O(1)$

理由如下: 引入了常数级别的空间