题解 | #正则表达式匹配#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @param pattern string字符串 
# @return bool布尔型
#
class Solution:
    def match(self , str: str, pattern: str) -> bool:
        # write code here
        dp=[
            [0 for j in range(len(pattern)+1)] for i in range(len(str)+1)
        ]
        dp[0][0]=1
        # 初始化，利用*和之前一个字符可以匹配空串的特性
        for j in range(2, len(pattern)+1):
            if pattern[j-1]=='*':
                dp[0][j]=dp[0][j-2]
        # dp[i][j]表示str[:i]和pattern[:j]是否匹配
        for i in range(1,len(str)+1):
            for j in range(1,len(pattern)+1):
                if pattern[j-1]!='.' and pattern[j-1]!='*':
                    if str[i-1]==pattern[j-1]:
                        dp[i][j]=dp[i-1][j-1]
                elif pattern[j-1]=='.':
                    dp[i][j]=dp[i-1][j-1]
                else:
                    # 默认*不会出现在0索引位置
                    if str[i-1]==pattern[j-2] or pattern[j-2]=='.':
                        # 匹配成功，继续向str前匹配
                        dp[i][j]=dp[i-1][j] or dp[i][j-2]
                    else:
                        # 去掉pattern*及前的字符
                        dp[i][j]=dp[i][j-2]
                print(f"i:{i} j:{j} dp:{dp[i][j]}")
        return dp[-1][-1]

dp含义：dp[i][j]表示str[:i]和pattern[:j]的匹配情况（0，1），注意dp[0][0]表示空串和空串的匹配情况，为了后续转移，这里设置为1

dp初始化：

主要针对i=0情况下，即对空串的匹配，例如str='' pattern='a*a*'这样子的情况

递推方程：

字母字符匹配：依赖于当前位置是否匹配和之前的字符串和模式是否匹配

if str[i-1]==pattern[j-1]: dp[i][j]=dp[i-1][j-1]

'.'匹配：依赖于之前的字符串和模式是否匹配

dp[i][j]=dp[i-1][j-1]

'*'匹配：

这里考虑pattern的前一个字符，因为默认*不会出现在第一个字符，所以这里也不需要判断pattern的索引的边界问题

如果pattern[j-2]==str[i]:代表*和上一个模式字符可以和str[:i]匹配：

但此时我们是可以选择匹配或者不匹配的。

那什么是不匹配的情况呢？

当pattern[j-2]！=str[i]:即当前*只能选择消去上一个模式字符pattern[j-2]的作用，由pattern[j-3]和str[i-1]的匹配结果转移而来。

dp[i][j]=dp[i][j-2]

由以上不匹配的情况，我们可以得到匹配情况的转移公式：

dp[i][j]=dp[i-1][j] or dp[i][j-2]

举一个样例理解一下

str='a' pattern='aa*'

我们先遍历str，再遍历pattern，那么dp的更新顺序应该是

dp[1][1]=1

dp[1][2]=0

dp[1][3]这时pattern[3-1-1]和str[1-1]相同，但是由dp[0][3]转移而来的话=0

但这个样例明显在匹配'a'和'aa*'时选择*匹配0次，即由dp[1][1]转移而来=1