Python DP


  • 0

    The only case make it more than a simple DP is that dp[i-1], dp[i1] must make sense(10 - 26) to be counted as a valid transforable state also dp[i-1] shouldn't be '0'

    class Solution(object):
        def numDecodings(self, s):
            if not s or s[0] == '0':
                return 0
            dp = [1 for i in xrange(len(s) + 1)]
            for i in xrange(1, len(s)):
                dp[i + 1] = (dp[i] if s[i] != '0' else 0) + (dp[i - 1] if 10 <= int(s[i-1] + s[i]) <= 26 else 0)
            return dp[-1]
    

Log in to reply
 

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