動(dòng)規(guī)就完事了。
首先，我們得想到返吻，由于letter + *結(jié)構(gòu)允許0和多個(gè)字符存在钙姊，所以處理的時(shí)候，應(yīng)該把它們看作一體癞季，也就是說，除了當(dāng)前字符，每時(shí)每刻都要考慮下一個(gè)字符是不是*赏廓。
而且，考慮一下兩個(gè)字符串在空的時(shí)候有什么行為：
-
s空了傍妒，沒關(guān)系幔摸，p可能有*表達(dá)式幫助匹配。 -
p空了颤练，必須看s有沒有空既忆。
所以，我們必須先進(jìn)行p的空檢測(cè)
最后嗦玖，考慮狀態(tài)轉(zhuǎn)移：
- 對(duì)于
*模式：- 零寬匹配患雇，
dp(i, j+2)。 - 有字符可匹配宇挫，
first_matched and dp(i + 1, j)苛吱，下一個(gè)狀態(tài)中依然會(huì)進(jìn)行*模式的判斷。
- 零寬匹配患雇，
- 對(duì)于非
*模式：-
s空的時(shí)候器瘪，那么肯定就匹配失敗了翠储。 - 否則，
first_matched and dp(i + 1, j + 1)橡疼。
-
在實(shí)現(xiàn)的時(shí)候援所，s空可以在狀態(tài)轉(zhuǎn)移之前，通過first_matched賦值的方式進(jìn)行處理欣除。
然后就是邏輯細(xì)節(jié)了：
class Solution:
def isMatch(self, s: str, p: str) -> bool:
d = {}
def dp(spt, ppt):
if (spt, ppt) not in d:
# 判斷p空
if ppt == len(p):
ans = spt == len(s)
else:
# 判斷第一個(gè)字符是否匹配或者s空
fm = spt < len(s) and p[ppt] in {s[spt], '.'}
# 對(duì)*模式的處理
if ppt + 1 < len(p) and p[ppt + 1] == '*':
ans = dp(spt, ppt + 2) or fm and dp(spt + 1, ppt)
# 對(duì)非*模式的處理
else:
ans = dp(spt + 1, ppt + 1) and fm
# 寫入字典
d[spt, ppt] = ans
return d[spt, ppt]
return dp(0, 0)
