题解 | 解密

class Solution:
    def numDecodings(self , s ):
        # write code here
        if s == '' or s[0] == '0':
            return 0
        dp = [1]*(len(s) + 1)
        dp[1] = 1
        for i in range(1,len(s)):
            count = 0
            if s[i - 1] != '0' and int(s[i - 1:i + 1]) <= 26:
                count += dp[i - 1]
            if s[i] != '0':
                count += dp[i]
            dp[i + 1] = count
        return dp[-1]

时间复杂度O(n)

空间复杂度O(n)

使用方法：动态规划记忆化搜索