题目描述

一个只包含 A-Z 的消息可以用如下方式编码成数字：

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

给定一个只包含数字的非空字符串，返回共有多少种解码方案。

样例

输入："12"
输出：2
解释：它可以被解码成 "AB" (1 2) 或者 "L" (12)。

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

C++ 代码

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        vector<int> dp(n+1);
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            if(s[i-1]!='0')dp[i]+=dp[i-1];
            if(i>=2)
            {
                int t=(s[i-2]-'0')*10+s[i-1]-'0';
                if(t>=10&&t<=26)dp[i]+=dp[i-2];
            }
        }
        return dp[n];
    }
};