class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        memo = dict()  
        def dp(i, j):
            if memo.get((i, j)) is not None:  #如果当前迭代有记录那么返回记录值
                return memo.get((i, j))

            if j == len(p):         #如果遍历p完成，那么结束
                return i == len(s)  #返回i是否等于s的长度

            first_match = False

            if i < len(s) and (p[j] == s[i] or p[j] == "."): #如果没有遍历完s,且满足两个相等条件

                first_match = True                           #那么负值为True

            if j <= len(p) - 2 and p[j + 1] == "*":  #如果p字符串下标小于等于s字符串长度减2并且p的下一个字符是*

                ans = dp(i, j + 2) or (first_match and dp(i + 1, j)) #那么迭代s[i],p[j+2]意识是p[j]这个字符不等于s[i]，跳过p[j]和*。 或者 s[i]==p[j]但是由于p[j+1]是*，所以s下标向下移动，p下标不变

            else: #如果p大于s字符串长度减2或者p[j+1]不是*

                ans = first_match and dp(i + 1, j + 1) #判断当前字符是否相等，并且迭代结果是否为True

            memo[(i, j)] = ans  #记录s[i]p[j]匹配结果

            return ans
        return dp(0, 0)