Python Memoization Solution


  • 0
    B
    def numDecodingsHelper(self,s,cache):
        if s in cache:
            return cache[s]
        #base case: s is empty
        if len(s) == 0:
            return 1 
        
            
        #divergence: 2 choices
        decodings =  0 if int(s[0]) == 0 else self.numDecodingsHelper(s[1:],cache)
        decodings += 0 if (len(s) < 2 or int(s[:2]) > 26 or int(s[:2]) < 10) else self.numDecodingsHelper(s[2:],cache)
        cache[s] = decodings
        return decodings
    
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        '''
        At the start of the encoded message, there are 2 paths you could follow: either decode the first 2 characters (provided they convert to an integer less than 27) or decode one character, and move on. 
        Divergence of path due to choice: recursion!
        And subproblems are similar, possible overlap: memoization
        '''
        cache = {}
        if len(s) == 0 or int(s) == 0:
            return 0
        return self.numDecodingsHelper(s, cache)

Log in to reply
 

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