class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0]=='0':
            return 0
        n = len(s)
        if n == 1: 
            return 1
        dp = [0]*n
        dp[0] = 1
        t = int(s[0:2])
        if 11 <= t and t <= 26 and t!=20:
            dp[1] = 2
        elif t == 20 or t == 10 or t%10 != 0:
            dp[1] = 1
        else:
            return 0
        for i in range(2,n):
            t = int(s[i-1:i+1])
            if t == 0: 
                return 0
            if t % 10 == 0:
                if 10 <= t and t <= 20:
                    dp[i] = dp[i-2]
                else:
                    return 0
            elif 1 <= t and t <= 9 or t >= 27:
                dp[i] = dp[i-1]
            elif 11 <= t and t <= 26:
                dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]

字符串 动态规划 中等 每日一题 👆我写的屑代码

#论一个好编码方式的重要性

https://leetcode-cn.com/problems/decode-ways/

👇官方题解

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        f = [1] + [0] * n
        for i in range(1, n + 1):
            if s[i - 1] != '0':
                f[i] += f[i - 1]
            if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:
                f[i] += f[i - 2]
        return f[n]

👇官方题解空间优化版

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        # a = f[i-2], b = f[i-1], c = f[i]
        a, b, c = 0, 1, 0
        for i in range(1, n + 1):
            c = 0
            if s[i - 1] != '0':
                c += b
            if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:
                c += a
            a, b = b, c
        return c