解题思路
「二维表」动态规划
具体详见代码里面的注释
https://leetcode-cn.com/problems/regular-expression-matching/
代码
class Solution:
def isMatch(self, s: str, p: str) -> bool:
rows, columns = len(s) + 1, len(p) + 1
matrix = [[False for _ in range(columns)][:] for _ in range(rows)]
for r in range(rows):
for c in range(columns):
if r == c == 0: # 空串空模式
matrix[r][c] = True
elif r == 0: # 仅空串
matrix[r][c] = p[c-1] == '*' and matrix[r][c-2]
elif c == 0: # 仅空模式
matrix[r][c] = False
else: # 有串有模式
if p[c-1] in ['.', s[r-1]]:
matrix[r][c] = matrix[r-1][c-1]
elif p[c-1] == '*':
if p[c-2] in ['.', s[r-1]]:
# 1.字符串进一格，模式进两格
# 2.字符串进一格，模式保持不变
# 3.字符串保持不变，模式进两格
matrix[r][c] = matrix[r-1][c-2] or matrix[r-1][c] or matrix[r][c-2]
else:
matrix[r][c] = matrix[r][c-2]
else:
matrix[r][c] = False
return matrix[len(s)][len(p)]
