Recursive solution in Python, with memoization


  • 0
    B
    def isMatchHelper(self, s, p, prev,cache):
        key = s+":"+p
        if key in cache:
            return cache[key]      
        #base case: both are empty:
        if len(s) == 0 and len(p) == 0:
            return True
        
        #base case: if p is empty and s isn't:
        if len(p) == 0:
            return False
        
        result = False
        
        #character match:
        if len(s) >= 1 and (s[0] == p[0] or p[0] == '.'):            
            if len(p) > 1 and p[1] == '*':
                result = self.isMatchHelper(s[1:], p[1:], p[0],cache) or self.isMatchHelper(s, p[2:], "",cache)
            else:
                result = self.isMatchHelper(s[1:], p[1:], p[0],cache)
            cache[key] = result
            return result
        
        #characters don't match
        
        if p[0] != '*':
            if len(p) == 1 or p[1] != '*':
                return False
            result = self.isMatchHelper(s, p[2:], "",cache)
            cache[key]  = result
            return result
        
        if p[0] == '*':
            if len(s) >=1 and (prev == s[0] or prev == '.'):
                result = (self.isMatchHelper(s[1:], p[1:], "",cache) or self.isMatchHelper(s[1:], p, prev, cache) or self.isMatchHelper(s, p[1:], "" ,cache))
            else:
                result =  (self.isMatchHelper(s, p[1:], "" ,cache))
                
            cache[key] = result
            return result
                              
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        '''
        go character by character: a couple of situations:
        i: character matches (either same char or .): trim one character from each and go on, or trim 2 characters from p and go on
        ii: characer does not match but isnt *: check if next char is *, if so, trim 2 from p and go on
        iii: character has *: check if prev character of p matches current char of s: if so, do as part i and ii. If not, trim one characer from p. 
        
        '''
        cache = {}
        return self.isMatchHelper(s, p, "", cache)

Log in to reply
 

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