这篇文章上次修改于 746 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

1 解码方法

有一个消息包含A-Z通过以下规则编码

'A' -> 1
'B' -> 2
...
'Z' -> 26

现在给你一个加密过后的消息，问有几种解码的方式。

输入: "12"
输出: 2
解释: 它可以被解码为 AB (1 2) 或 L (12).

class Solution {
public:
    /**
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    int numDecodings(string &s) {
        // dp(i) = dp(i - 1) + (dp(i - 2) && s[i - 1][i] is a number);
        int n = s.size();
        if (n == 0) return 0;
        vector<int> dp(n, 0);
        dp[0] = s[0] == '0' ? 0 : 1;
        for (int i = 1; i < n; i++) {
            if (s[i] != '0') {
                dp[i] = dp[i - 1];
            }
            int m = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if (m >= 10 && m <= 26) {
                if (i == 1) {
                    dp[i] += 1;
                } else {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[n - 1];
    }
};

参考

https://www.bilibili.com/video/BV1nt4y1Y7n7?p=2&spm_id_from=pageDriver