正则表达式匹配

2022-02-09

leetcode题目链接：这里

总结一下自己从这道题中学习到的几个要点。

一、要考虑”空”这种情况

字符串匹配，要考虑空串的情况，本题中，考虑了空的情况后，在代码上会有两个地方体现。第一个就是初始化矩阵f时，其维度要比字符串长度大1，位置0表示 的就是字符串长度为0的情况。 第二个就是，在使用动态规划填充矩阵f时，矩阵的索引和字符串的索引对应关系会容易搞错。矩阵中的索引1，对应的字符串的索引就是0。 这一点在计算两个字符串的编辑距离时也有体现。

二、状态转移方程中“*”号的转移公式

根据动态规划，要确定f[i][j]的状态转移公式。i表示的是原字符串s中的索引为i-1的字符，j表示的模式字符串p中的索引为j-1的字符。 因为“*”号匹配涉及到p中前一个字符，所以要分两种情况进行讨论：

第一种情况是s[i-1] != p[j-2]，那么此时有： f[i][j] = f[i][j-2] 这相当于是直接舍弃掉p中前面不匹配的字符和当前的“*”号。

第二种情况是s[i-1]==p[j-2]，此时又需要进一步分两种情况讨论： 一种是和上面一样，舍弃掉p中前面匹配的字符和当前的“*”号。这时有： f[i][j] = f[i][j-2] 第二种就是不舍弃p中前面匹配的字符和当前的“*”号，那这就有个问题，要用它匹配掉s中多少个相同的字符呢？ 比较聪明的一个想法，就是进一步使用递归的思想来解决。 就是匹配掉s中的一个字符后，剩余的字符串s[:i-1]仍然和现在的p[:j]进行匹配即可。 f[i][j] |= f[i-1][j]

三、总结

这道题是一个符合“逐步匹配”特点的题，凡是有这样特点的题目，都可以考虑使用动态规划来解决。

四、代码

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        f = [[False]*(n+1) for _ in range(m+1)]
        f[0][0] = True

        def matches(i, j):
            if i == 0:
                return False
            if p[j-1] == ".":
                return True
            return s[i-1] == p[j-1]
        
        for i in range(m+1):
            for j in range(1, n+1):
                if p[j-1] == "*":
                    f[i][j] |= f[i][j-2]
                    if matches(i, j-1):
                        f[i][j] |= f[i-1][j]
                else:
                    if matches(i, j):
                        f[i][j] |= f[i-1][j-1]
        return f[m][n]