leetcode [91] 解码方法

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

一条包含字母 A-Z 的消息通过以下方式进行了编码：

‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

来自题解:

动态规划，如果当前值为0，并且上一个值是1或2，那么dp值为dp[i-2]的值，如110的例子。如果当前值不为0，即匹配1*或者26范围内，那么dp值为dp[i-1]+dp[i-2]，即当前值独立解析和当前值和前一位一同解析的解之和。不在以上情况的dp值与dp[i-1]值相同。

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == '0':
            return 0

        dp = [0] * (len(s) + 1)
        dp[0] = dp[1] = 1
        for i in range(2, len(dp)):
            if s[i - 1] == '0':
                if s[i - 2] in '12':
                    dp[i] = dp[i - 2]
                else:
                    return 0
            else:
                if s[i - 2] == "1" or s[i - 2] == "2" and "1" <= s[i - 1] <= "6":
                    dp[i] = dp[i - 1] + dp[i - 2]
                else:
                    dp[i] = dp[i - 1]
        return dp[-1]