正则表达式

对于字符串匹配的问题，正则表达式绝对是一个大杀器，同时在实际的项目中正则表达式也是很好的一个工具，比方说，在语音处理方面，如果NLU的模型训练的不好，其实际的效果甚至不如正则表达式。

正则表达式规则

or

| 可以用来表示or的关系，例如：gray|grey can match “gray” or “grey”.

Grouping

括号用来定义区域的范围，例如：gray|grey and gr(a|e)y are equivalent patterns which both describe the set of “gray” or “grey”.

Quantificaton

? 匹配零个或一个在？之前的字符。例如：colou?r matches both “color” and “colour”.
匹配零个或多个在之前的字符。例如：ab*c matches “ac”, “abc”, “abbc”, “abbbc”, and so on.
+ 匹配一个或多个在+之前的字符
{n}匹配在其之前的字符n次
{min，}匹配在其之前的字符至少min次
{min，max}匹配在其之前的字符至少min次，至多max次

Wildcard 通配、

.(点)可以匹配除了换行符之外的所有字符

Example

a|b* denotes {ε, “a”, “b”, “bb”, “bbb”, …}
(a|b)* denotes the set of all strings with no symbols other than “a” and “b”, including the empty string: {ε, “a”, “b”, “aa”, “ab”, “ba”, “bb”, “aaa”, …}
ab*(c|ε) denotes the set of strings starting with “a”, then zero or more “b”s and finally optionally a “c”: {“a”, “ac”, “ab”, “abc”, “abb”, “abbc”, …}
(0|(1(01*0)*1))* denotes the set of binary numbers that are multiples of 3: { ε, “0”, “00”, “11”, “000”, “011”, “110”, “0000”, “0011”, “0110”, “1001”, “1100”, “1111”, “00000”, … }

例题

468. 验证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 是无效的。

说明: 你可以认为给定的字符串里没有空格或者其他特殊字符。

示例 1:

输入: “172.16.254.1”

输出: “IPv4”

解释: 这是一个有效的 IPv4 地址, 所以返回 “IPv4”。

示例 2:

输入: “2001:0db8:85a3:0:0:8A2E:0370:7334”

输出: “IPv6”

解释: 这是一个有效的 IPv6 地址, 所以返回 “IPv6”。

示例 3:

输入: “256.256.256.256”

输出: “Neither”

解释: 这个地址既不是 IPv4 也不是 IPv6 地址。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/validate-ip-address

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Python提供了专门的库用来判断是否是IPv4或是IPv6

from ipaddress import ip_address, IPv6Address
class Solution:
    def validIPAddress(self, IP: str) -> str:
        try:
            return "IPv6" if type(ip_address(IP)) is IPv6Address else "IPv4"
        except ValueError:
            return "Neither"

正则表达式

import re
class Solution:
    chunk_IPv4 = r'([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])'
    patten_IPv4 = re.compile(r'^(' + chunk_IPv4 + r'\.){3}' + chunk_IPv4 + r'$')
    chunk_IPv6 = r'([0-9a-fA-F]{1,4})'
    patten_IPv6 = re.compile(r'^(' + chunk_IPv6 + r'\:){7}' + chunk_IPv6 + r'$')
    def validIPAddress(self, IP: str) -> str:        
        if self.patten_IPv4.match(IP):
            return "IPv4"
        return "IPv6" if self.patten_IPv6.match(IP) else "Neither"

时间复杂度O(1), 空间复杂度O(1)

分治法

class Solution:
    def validate_IPv4(self, IP: str) -> str:
        nums = IP.split('.')
        for x in nums:
            # Validate integer in range (0, 255):
            # 1. length of chunk is between 1 and 3
            if len(x) == 0 or len(x) > 3:
                return "Neither"
            # 2. no extra leading zeros
            # 3. only digits are allowed
            # 4. less than 255
            if x[0] == '0' and len(x) != 1 or not x.isdigit() or int(x) > 255:
                return "Neither"
        return "IPv4"

    def validate_IPv6(self, IP: str) -> str:
        nums = IP.split(':')
        hexdigits = '0123456789abcdefABCDEF'
        for x in nums:
            # Validate hexadecimal in range (0, 2**16):
            # 1. at least one and not more than 4 hexdigits in one chunk
            # 2. only hexdigits are allowed: 0-9, a-f, A-F
            if len(x) == 0 or len(x) > 4 or not all(c in hexdigits for c in x):
                return "Neither"
        return "IPv6"

    def validIPAddress(self, IP: str) -> str:
        if IP.count('.') == 3:
            return self.validate_IPv4(IP)
        elif IP.count(':') == 7:
            return self.validate_IPv6(IP)
        else:
            return "Neither"

时间复杂度O(N),空间复杂度O(1)

笔者在做这道题时，采用C++费了半天劲才通过。但代码依旧不是特别的优雅

class Solution {
public:
     bool isIPV4(string IP)
    {
        if(IP.size() < 7 || IP[0] == '.' || IP[IP.size() - 1] == '.')
            return false;

            stringstream ss(IP);
            string item;
            vector<std::string>splitstr;
            while(getline(ss, item,'.'))
            {
                splitstr.push_back(item);
            }

            if(splitstr.size() != 4)
                return false;

            for(auto &str : splitstr)
            {
                if(str.size() > 3 || str.size() == 0 || (str[0] == '0' && str.size() != 1))
                    return false;

                for(auto &ch : str)
                {
                    if(!(ch >= '0' && ch <= '9'))
                        return false;
                }

                int tmp = stoi(str);
                if(tmp < 0 || tmp > 255)
                    return false;


            }

            return true;
    }

    bool isIPV6(string IP)
    {
        if(IP.size() < 15  || IP[0] == ':' || IP[IP.size() - 1] == ':')
            return false;

        stringstream ss(IP);
        string item;
        vector<std::string>splitstr;
        while(getline(ss, item,':'))
        {
            splitstr.push_back(item);
        }

        if(splitstr.size() != 8)
            return false;

        for(auto &str : splitstr)
        {
            if(str.size() > 4 || str.size() == 0)
                return false;
            for(auto &ch : str)
            {
                if(!((ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'f') || (ch >= 'A' && ch <= 'F')))
                    return false;
            }
        }

        return true;
    }
    string validIPAddress(string IP) {
        if(IP.size() <= 4)
            return "Neither";

        if(isIPV4(IP))
            return "IPv4";

        if(isIPV6(IP))
            return "IPv6";

        return "Neither";
    }
};