[Python] Top down dynamic programming
We track which character we are up to comparing between both strings, by using s_idx and p_idx\n\nThe recurrence relation is constructed from the following:\n I
We track which character we are up to comparing between both strings, by using `s_idx` and `p_idx`\n\nThe recurrence relation is constructed from the following:\n* If the current character of p is "\\*", we can...\n\t* Treat \\* as empty by skipping over it - `is_match(s, p, s_idx, p_idx + 1)`\n\t* Treat \\* as many characters - `is_match(s, p, s_idx + 1, p)`\n\t* Treat \\* as one character, so we increment both s_idx and p_idx by 1 - `is_match(s, p, s_idx + 1, p_idx + 1)`\n* Otherwise, the current character is `?` or a letter, so...\n    * For both `?` and letter, we simply advance the indexes by 1 - `is_match(s, p, s_idx + 1, p_idx + 1)`\n\n```\nclass Solution:\n    def is_match(self, s, p, s_idx, p_idx):\n\t    # reached end of both strings, it must have matched\n        if s_idx >= len(s) and p_idx >= len(p):\n            return True\n  \n\t\t# reached end of s, but there are still characters in p remaining\n        if s_idx >= len(s) and p_idx < len(p):\n\t\t    # if any character remaining in p, is not "*"\n\t\t\t# that means we have nothing in s to match, so return False\n            for i in range(p_idx, len(p)):\n                if p[i] != "*":\n                    return False\n            return True\n        \n\t\t# if we have reached end of p, but not end of s, this means\n\t\t# we do not have sufficient characters in the pattern to match s\n\t\t# return false\n        if s_idx < len(s) and p_idx >= len(p):\n            return False\n        \n        if (s_idx, p_idx) in self.dp:\n            return self.dp[(s_idx, p_idx)]\n        \n        s_char = s[s_idx]\n        p_char = p[p_idx]\n        \n        if p_char.isalpha() and s_char != p_char:\n            return False\n        \n        if p_char == "*":\n            skip_star = self.is_match(s, p, s_idx, p_idx + 1)\n            use_star = self.is_match(s, p, s_idx + 1, p_idx)\n            not_use_star = self.is_match(s, p, s_idx + 1, p_idx + 1)\n            \n            self.dp[(s_idx, p_idx)] = skip_star or use_star or not_use_star\n            return self.dp[(s_idx, p_idx)]\n        \n        self.dp[(s_idx, p_idx)] = self.is_match(s, p, s_idx + 1, p_idx + 1)\n        return self.dp[(s_idx, p_idx)]        \n\n\n    def isMatch(self, s: str, p: str) -> bool:        \n        self.dp = {}\n        return self.is_match(s, p, 0, 0)\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Python']