动规就完事了。
首先，我们得想到，由于letter + *结构允许0和多个字符存在，所以处理的时候，应该把它们看作一体，也就是说，除了当前字符，每时每刻都要考虑下一个字符是不是*。
而且，考虑一下两个字符串在空的时候有什么行为：
-
s空了，没关系，p可能有*表达式帮助匹配。 -
p空了，必须看s有没有空。
所以，我们必须先进行p的空检测
最后，考虑状态转移：
- 对于
*模式：- 零宽匹配，
dp(i, j+2)。 - 有字符可匹配，
first_matched and dp(i + 1, j)，下一个状态中依然会进行*模式的判断。
- 零宽匹配，
- 对于非
*模式：-
s空的时候，那么肯定就匹配失败了。 - 否则，
first_matched and dp(i + 1, j + 1)。
-
在实现的时候，s空可以在状态转移之前，通过first_matched赋值的方式进行处理。
然后就是逻辑细节了：
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:
# 判断第一个字符是否匹配或者s空
fm = spt < len(s) and p[ppt] in {s[spt], '.'}
# 对*模式的处理
if ppt + 1 < len(p) and p[ppt + 1] == '*':
ans = dp(spt, ppt + 2) or fm and dp(spt + 1, ppt)
# 对非*模式的处理
else:
ans = dp(spt + 1, ppt + 1) and fm
# 写入字典
d[spt, ppt] = ans
return d[spt, ppt]
return dp(0, 0)
