Python solution with explanation


  • -1
    F

    Easily understandable, 'One' stands for decode in 1 digit, 'two' stands for decode in 2 digits.

    class Solution(object):
    def numDecodings(self, s):
        if len(s)==0: return 0
        if len(s)==1: return 1 if int(s) in range(1,10) else 0
        dp=[0]*len(s)
        dp[0]=1 if int(s[0]) in range(1,10) else 0
        one=1 if int(s[0]) in range(1,10) and int(s[1]) in range(1,10) else 0
        two=1 if int(s[:2]) in range(10,27) else 0
        dp[1]=one+two
        for i in xrange(2,len(s)):
            one=dp[i-1] if int(s[i]) in range(1,10) else 0
            two=dp[i-2] if int(s[i-1:i+1]) in range(10,27) else 0
            dp[i]=one+two
        return dp[-1]

Log in to reply
 

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