LeetCode_91. 解碼方法

題目描述：

一條包含字母 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) 。      

class Solution {
public:
    int numDecodings(string s) {
        int len=s.size();
        vector<int> dp(len+1);
        dp[len]=1;//初始化
        for(int i=len-1;i>=0;i--){
            if(s[i]=='0')
                dp[i]=0;//0無法單獨作為一個數而且0也沒有辦法作為十位數
            else{
                dp[i]=dp[i+1];
                if(i+2<=len&&((s[i]-'0')*10+(s[i+1]-'0')<=26))
                    dp[i]+=dp[i+2];
            }
        }
        return dp[0];
    }
};