image.png
image.png
image.png
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s) + 1, len(p) + 1
dp = [[False] * n for _ in range(m)]
dp[0][0] = True
# 初始化首行
for j in range(2, n, 2):
dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'
# 状态转移
for i in range(1, m):
for j in range(1, n):
if p[j - 1] == '*':
if dp[i][j - 2]: dp[i][j] = True # 1.
elif dp[i - 1][j] and s[i - 1] == p[j - 2]: dp[i][j] = True # 2.
#前面的已经匹配了，再增加一个S_i-1和P_n-2相等，只需要把之前代表重复N次的*想成重复N+1次即可实现
elif dp[i - 1][j] and p[j - 2] == '.': dp[i][j] = True # 3.同上
else:
if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]: dp[i][j] = True # 1.
elif dp[i - 1][j - 1] and p[j - 1] == '.': dp[i][j] = True # 2.
return dp[-1][-1]
方法二
image.png
image.png
image.png
image.png
image.png
image.png
代码
image.png
