91 Decode Ways

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

solution

# 状态转移的原因在于: 存在两位的字符(10-26), 斐波那契

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == "0":  # 非法，中途的非法通过条件判断        
            return 0
        
        dp = [0] * (len(s) + 1)             
        dp[0] = 1
        dp[1] = 1
        
        for i in range(2, len(s) + 1):
            if 1 <= int(s[i-1]) <= 9:
                dp[i] += dp[i - 1]
            if 10 <= int(s[i - 2] + s[i - 1]) <= 26 :
                dp[i] += dp[i - 2]
        return dp[-1]

时间复杂度：O(n) 空间复杂度：O(n)

follow up

639 Decode Ways II