Simple Python DP Solution


  • 0
    P
    def numDecodings(self, s):
        
        if not s or not int(s[0]) : return 0
       
        dp = [1 for i in range(len(s)+1)]
        test = s[0]
        
        for i in range(2, len(s)+1) :
            test = test[-1] + s[i-1]
            t = int(test)
          
            if not t % 10 : 
                if not t or t / 10 >= 3:
                    return 0
                else :
                    dp[i] = dp[i-2]
            elif t > 26 or t < 10:
                dp[i] = dp[i-1]
                
            else : dp[i] = dp[i-1] + dp[i-2]
        
        return dp[-1]

  • 0
    D

    This uses O(n) memory for dp but since we only look back that last two entries in dp, we can change this to use constant memory.

    class Solution(object):
        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            if not s or s[0] == '0':
                return 0
            
            dp = [1, 1]
    
            for i in range(2, len(s)+1) :
                num = int(s[i-2:i])
    
                if num % 10 == 0:
                    if num == 0 or num > 20:
                        # hit a snag like 00, 30, 40, *0
                        return 0
                    else:
                        # num is 10 or 20, must take double
                        v = dp[-2]
                elif num > 26 or num < 10:
                    # num has to be taken as a single
                    v = dp[-1]
                else:
                    # num can be a single or a double
                    v = dp[-1] + dp[-2]
                dp.append(v)
                dp.pop(0)
    
            return dp[-1]
    

Log in to reply
 

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