对于字符串匹配的问题，正则表达式绝对是一个大杀器，同时在实际的项目中正则表达式也是很好的一个工具，比方说，在语音处理方面，如果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

  1. from ipaddress import ip_address, IPv6Address
  2. class Solution:
  3.     def validIPAddress(self, IP: str) -> str:
  4.         try:
  5.             return "IPv6" if type(ip_address(IP)) is IPv6Address else "IPv4"
  6.         except ValueError:
  7.             return "Neither"

正则表达式

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

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

分治法

  1. class Solution:
  2.     def validate_IPv4(self, IP: str) -> str:
  3.         nums = IP.split('.')
  4.         for x in nums:
  5.             # Validate integer in range (0, 255):
  6.             # 1. length of chunk is between 1 and 3
  7.             if len(x) == 0 or len(x) > 3:
  8.                 return "Neither"
  9.             # 2. no extra leading zeros
  10.             # 3. only digits are allowed
  11.             # 4. less than 255
  12.             if x[0] == '0' and len(x) != 1 or not x.isdigit() or int(x) > 255:
  13.                 return "Neither"
  14.         return "IPv4"
  16.     def validate_IPv6(self, IP: str) -> str:
  17.         nums = IP.split(':')
  18.         hexdigits = '0123456789abcdefABCDEF'
  19.         for x in nums:
  20.             # Validate hexadecimal in range (0, 2**16):
  21.             # 1. at least one and not more than 4 hexdigits in one chunk
  22.             # 2. only hexdigits are allowed: 0-9, a-f, A-F
  23.             if len(x) == 0 or len(x) > 4 or not all(c in hexdigits for c in x):
  24.                 return "Neither"
  25.         return "IPv6"
  27.     def validIPAddress(self, IP: str) -> str:
  28.         if IP.count('.') == 3:
  29.             return self.validate_IPv4(IP)
  30.         elif IP.count(':') == 7:
  31.             return self.validate_IPv6(IP)
  32.         else:
  33.             return "Neither"

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

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

  1. class Solution {
  2. public:
  3.      bool isIPV4(string IP)
  4.     {
  5.         if(IP.size() < 7 || IP[0] == '.' || IP[IP.size() - 1] == '.')
  6.             return false;
  8.             stringstream ss(IP);
  9.             string item;
  10.             vector<std::string>splitstr;
  11.             while(getline(ss, item,'.'))
  12.             {
  13.                 splitstr.push_back(item);
  14.             }
  16.             if(splitstr.size() != 4)
  17.                 return false;
  19.             for(auto &str : splitstr)
  20.             {
  21.                 if(str.size() > 3 || str.size() == 0 || (str[0] == '0' && str.size() != 1))
  22.                     return false;
  24.                 for(auto &ch : str)
  25.                 {
  26.                     if(!(ch >= '0' && ch <= '9'))
  27.                         return false;
  28.                 }
  30.                 int tmp = stoi(str);
  31.                 if(tmp < 0 || tmp > 255)
  32.                     return false;
  35.             }
  37.             return true;
  38.     }
  40.     bool isIPV6(string IP)
  41.     {
  42.         if(IP.size() < 15  || IP[0] == ':' || IP[IP.size() - 1] == ':')
  43.             return false;
  45.         stringstream ss(IP);
  46.         string item;
  47.         vector<std::string>splitstr;
  48.         while(getline(ss, item,':'))
  49.         {
  50.             splitstr.push_back(item);
  51.         }
  53.         if(splitstr.size() != 8)
  54.             return false;
  56.         for(auto &str : splitstr)
  57.         {
  58.             if(str.size() > 4 || str.size() == 0)
  59.                 return false;
  60.             for(auto &ch : str)
  61.             {
  62.                 if(!((ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'f') || (ch >= 'A' && ch <= 'F')))
  63.                     return false;
  64.             }
  65.         }
  67.         return true;
  68.     }
  69.     string validIPAddress(string IP) {
  70.         if(IP.size() <= 4)
  71.             return "Neither";
  73.         if(isIPV4(IP))
  74.             return "IPv4";
  76.         if(isIPV6(IP))
  77.             return "IPv6";
  79.         return "Neither";
  80.     }
  81. };