解題思路
「二維表」動(dòng)態(tài)規(guī)劃
具體詳見代碼里面的注釋
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.字符串進(jìn)一格捞高，模式進(jìn)兩格
# 2.字符串進(jìn)一格，模式保持不變
# 3.字符串保持不變痰腮，模式進(jìn)兩格
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)]
