Leetcode 44 Solution

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        memo = {}

        def match(s, p, i, j):
            key = (i, j)

            if key in memo:
                return memo[key]

            if i == len(s) and j == len(p):
                return True

            def check(s, p, i, j):
                while i < len(s):
                    if j == len(p):
                        return False

                    if p[j] == '*':
                        while j + 1 < len(p) and p[j + 1] == '*':
                            j += 1

                        k = i
                        while k <= len(s):
                            if match(s, p, k, j + 1):
                                return True
                            k += 1
                        return False

                    if p[j] == '?':
                        return match(s, p, i + 1, j + 1)

                    if i == len(s) or j == len(p):
                        return False

                    if s[i] == p[j]:
                        i += 1
                        j += 1
                    else:
                        return False

                for k in range(j, len(p)):
                    if p[k] != '*':
                        return False
                return True

            memo[key] = check(s, p, i, j)
            return memo[key]

        return match(s, p, 0, 0)