Участник:Mugadzhir/decode-ways

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution(object):
    def numDecodings(self, s):
        ls = len(s)
        if ls == 0:
            return 0
        if ls == 1:
            if s == "0":
                return 0
            else:
                return 1
        if s[0] == "0": return 0
        dp = [1 for i in range(ls+1)]
        dp[0]= 1
        dp[1]= 1
        for j in range(2,ls+1):
            i = j-1
            if s[i] == "0":
                if s[i-1] =="1" or s[i-1] == "2":
                    dp[j]=dp[j-2]
                else: return 0                
            elif int(s[i-1])*10 + int(s[i] ) <= 26:
                if s[i-1]!= "0":
                    dp[j] = dp[j-1]+dp[j-2]
                else:
                    dp[j] = dp[j-1]
            else:
                dp[j] = dp[j-1]
        return dp[ls]