Learning On the Way

10. Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '' where: '.' Matches any single character. '' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

def isMatch(self, s: str, p: str) -> bool: 
    @cache 
    def match(i, j): 
        if j >= len(p): # Empty pattern only match with empty string 
            return i >= len(s) 
        firstMatch = i < len(s) and p[j] in ['.', s[i]] 
        if j + 1 < len(p) and p[j + 1] == '*': 
            if match(i, j + 2): # In this case, * means zero times
                return True 
            return firstMatch and match(i + 1, j)
        else: 
            return firstMatch and match(i + 1, j + 1) 
    return match(0, 0)