class Solution:
    def numDecodings(self, s):
        if s == "": return 0
        dp = [0 for x in range(len(s)+1)]
        dp[0] = 1
        for i in range(1, len(s)+1):
            if s[i-1] != "0":
                dp[i] += dp[i-1]
            if i != 1 and s[i-2:i] < "27" and s[i-2:i] > "09":  #"01"ways = 0
                dp[i] += dp[i-2]
        return dp[len(s)]
"""
class Solution:
    def numDecodings(self, s):
        self.ans=0
        def helper(s,start,carry):
            if len(s)==start:
                if not carry:
                    self.ans+=1
                return
            if carry:
                if 0<int(s[start-1]+s[start])<=26:
                    helper(s,start+1,0)
                else:
                    return False
            else:
                if s[start]!="0":
                    helper(s,start+1,0)
                    helper(s,start+1,1)
            return
        helper(s,0,0)
        return self.ans
s=Solution()
print(s.numDecodings("12"))
"""

用recursive一般会超时，考虑dp 速度快