[LeetCode] 10. Regular Expression Matching

Problem : https://leetcode.com/problems/regular-expression-matching/

Time Complexity = O( len(s) * len(p)  )

Space Complexity = O( len(s) * len(p) )

 
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        
        @lru_cache(maxsize = None)
        def helper(i, j):
            if j >= len(p): return i >= len(s)
            
            isMatched = i < len(s) and (s[i] == p[j] or p[j] == '.')
            
            if isMatched and helper(i+1, j+1):
                return True
            
            if j + 1 < len(p) and p[j+1] == '*':
                
                # use '.*' or 'x*' to match nothing
                if helper(i, j+2):
                    return True
                
                # use '.*' or 'x*' to match current char and keep using it to match following chars
                if isMatched and helper(i+1, j):
                    return True
            
            return False
        
        return helper(0, 0)