Easy Python DP solution


  • 0

    The relation is :

    DP[i] = DP[i-1]   +   DP[i-2]
               \                  \___________(if   str[i-2] exists and 10<= int(str[i-1] + str[i]))<=26  )
                 \___________(If str[i-1] exists and str[i] != '0' )
    
    
    def numDecodings(self, s):
        if not s:
            return 0
    
        dp = [0]*(len(s)+1)
        dp[0] = 1
        for i in xrange(len(s)):
            if self.isValid(s[i]):
                dp[i+1] = dp[i-1+1]
            if i>0 and self.isValid(s[i-1:i+1]):
                dp[i+1] += dp[i-2+1] 
        return dp[-1]
    
    def isValid(self,s):
        if int(s) == 0:
            return False
        if len(s) == 1 and 0<int(s) <10:
            return True
        if len(s) == 2 and 10 <= int(s) <= 26:
            return True

Log in to reply
 

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