class Solution:

    def isMatch(self, s: str, p: str) -> bool:
        # if len(p) == 0:
        #     return s == ''
        # first = len(s) > 0 and p[0] in {s[0], '.'}

        # if len(p)>1 and p[1] == '*':
        #     return self.isMatch(s, p[2:]) or (first and self.isMatch(s[1:], p))

        # return first and self.isMatch(s[1:], p[1:])

        self.dp = dict()

        def match(i, j):
            if (i, j) in self.dp:
                return self.dp[(i, j)]
            if j == len(p):
                return i == len(s)

            first = i < len(s) and j < len(p) and p[j] in {s[i], '.'}

            if j < len(p) - 1 and p[j + 1] == '*':
                self.dp[(i, j)] = match(i, j + 2) or (first and match(i + 1, j))
                return self.dp[(i, j)]

            self.dp[(i, j)] = first and match(i + 1, j + 1)
            return self.dp[(i, j)]

        return match(0, 0)


if __name__ == '__main__':
    s = Solution()
    print(s.isMatch('aa', 'a*'))
