10. Regular Expression Matching

We can implement this with caching in order to do this recursively.

class Solution:
    @lru_cache
    def isMatch(self, s: str, p: str) -> bool:
        if not p: 
            return not s
        if not s: 
            return len(p) > 1 and p[1] == '*' and self.isMatch(s, p[2:])
        matched = (p[0] == '.' or p[0] == s[0])
        if len(p) > 1 and p[1] == '*':
            return (matched and self.isMatch(s[1:], p)) or self.isMatch(s, p[2:])
        return matched and self.isMatch(s[1:], p[1:])