Recursive Python Solution with Cache (Memoization)


  • 0
    A

    I found this method simpler to understand than the dynamic programming solutions using a two dimensional table.

    This method differs in that before a recursive call to isMatch, the algorithm checks to see if the next state already exists in the cache / dictionary and uses that precomputed value instead. If the next state is not in the dictionary, it computes it recursively and stores the result in the cache for the future.

    In terms of code quality and variable names, there could be some improvement, but I felt the algorithm is easier to understand.

    Here is the code:

    class Solution(object):
        
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            return self.isMatchHelper(s, p, {})
            
        def isMatchHelper(self, s, p, cache):
            # if at the end of the pattern, we must also be at the end of the text
            if not p:
                return not s
            
            curr_match = bool(s) and p[0] in {s[0], '.'}
            
            if len(p) >= 2 and p[1] == '*':
                skip = False
                if (s, p[2:]) in cache:
                    skip = cache[(s, p[2:])]
                else:
                    skip = self.isMatchHelper(s, p[2:], cache) 
                    cache[(s, p[2:])] = skip
                
                if curr_match:
                    if (s[1:], p) in cache:
                        delete = cache[(s[1:], p)]
                    else:
                        delete = self.isMatchHelper(s[1:], p, cache)
                        cache[(s[1:], p)] = delete
                        
                return skip or (curr_match and delete)
            
            else:
                if curr_match:
                    if (s[1:], p[1:]) in cache:
                        general = cache[(s[1:], p[1:])]
                    else:
                        general = self.isMatchHelper(s[1:], p[1:], cache)
                        cache[(s[1:], p[1:])] = general
                        
                return curr_match and general    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.