class Solution(object):
    def isMatch(self,s,p):
        n=len(p)
        m=len(s)
        memory=[[False]*(m+1) for _ in range(n+1)]
        memory[n][m]=True

        if m==0 and n==2 and p[-1]=='*':
        # 边界存疑
            return True



        for i1 in range(n-1,-1,-1):

            for i2 in range(m-1,-1,-1):

                cur=memory[i1][i2]

                if p[i1]=='.' or p[i1]==s[i2]:

                    cur=memory[i1+1][i2+1]

                if i1+1<n and p[i1+1]=='*':

                    cur=cur or memory[i1+2][i2]
                    #零次
                    if p[i1]=='.' or p[i1]==s[i2]:

                        cur=cur or memory[i1+2][i2+1] or memory[i1][i2+1]

                memory[i1][i2]=cur

        return memory[0][0]