Neat python DP. Beat 100%


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

  • 0
    S

    And we can do O(1) space simply since we only need the most recent two values in dp array.


Log in to reply
 

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