正则表达式匹配

发表于 更新于 分类于 阅读次数：

正则表达式匹配（难度：困难）

1

转自：

作者：labuladong 链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/ji-yu-guan-fang-ti-jie-gen-xiang-xi-de-jiang-jie-b/ 来源：力扣（LeetCode）

一、处理点号「.」通配符

点号可以匹配任意一个字符，其实是最简单的：

1
2
3
4
def isMatch(text, pattern) -> bool:
    if not pattern: return not text
    first_match = bool(text) and pattern[0] in {text[0], '.'}
    return first_match and isMatch(text[1:], pattern[1:])

二、处理「*」通配符

星号通配符可以让前一个字符重复任意次数，包括零次。那到底是重复几次呢？这需要计算机暴力穷举来算，假设重复 N 次吧。写递归的技巧是管好当下，之后的事抛给递归。具体到这里，不管 N 是多少，当前的选择只有两个：匹配 0 次、匹配 1 次。所以可以这样处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
def isMatch(text, pattern) -> bool:
    if not pattern: return not text
    first_match = bool(text) and pattern[0] in {text[0], '.'}
    if len(pattern) >= 2 and pattern[1] == '*':
        # 发现 '*' 通配符
        return isMatch(text, pattern[2:]) or \
                first_match and isMatch(text[1:], pattern)
    	# 解释：如果发现有字符和 '*' 结合，
        	# 或者匹配该字符 0 次，然后跳过该字符和 '*'
        	# 或者当 pattern[0] 和 text[0] 匹配后，移动 text
            
    else:
        return first_match and isMatch(text[1:], pattern[1:])

可以看到，我们是通过保留 pattern 中的「*」，同时向后推移 text，来实现「*」将字符重复匹配多次的功能。

三、动态规划

暴力解法
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p:
            return not s
        
        first = s and p[0] in {s[0],'.'}

        if len(p) >= 2 and p[1]=='*':
            return self.isMatch(s,p[2:]) or (first and self.isMatch(s[1:],p))
        else:
            return first and self.isMatch(s[1:],p[1:])
2
优化解法

使用两个变量 i, j 记录当前匹配到的位置，从而避免使用子字符串切片，并且将 i, j 存入memo，避免重复计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        memo = {}

        def dp(i,j):
            if (i,j) in memo:
                return memo[(i,j)]
            
            if j==len(p):
                return i==len(s)
            
            first = i < len(s) and p[j] in {s[i],'.'}

            if len(p) >= j+2 and p[j+1]=='*':
                return dp(i,j+2) or (first and dp(i+1,j))
            else:
                return first and dp(i+1,j+1)
            
            memo[(i,j)] = ans
            return ans
        
        return dp(0,0)
3

复杂度

时间复杂度：用 T 和 P 分别表示匹配串和模式串的长度。对于 i=0, ... , T 和 j=0, ... , P 每一个 dp(i, j) 只会被计算一次，所以后面每次调用都是 O(1)的时间。因此，总时间复杂度为 O(TP) 。

空间复杂度：我们用到的空间仅有 O(TP)个 boolean 类型的缓存变量。所以，空间复杂度为 O(TP) 。