解码方法-LintCode

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

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

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

样例：
给你的消息为12，有两种方式解码 AB(12) 或者 L(12). 所以返回 2。

思路：
动态规划，len为s的长度，取dp[]，大小为len+1，且dp[0]=1，dp[1]=1；
处理len为1时的情况，s为”0”，返回0，其他返回1；
用num表示位于i-2和i-1位置所组成的数。
状态转换方程为：
若11<=num<=26 && num!=0
dp[i]=dp[i−1]+dp[i−2]
若num是10的倍数，
num是10或者20
dp[i]=dp[i−2]
其他情况，返回0；
除此情况外
dp[i]=dp[i−1]

#ifndef C512_H
#define C512_H
#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
    /*
    * @param s: a string,  encoded message
    * @return: an integer, the number of ways decoding
    */
    int numDecodings(string &s) {
        // write your code here
        if (s.empty())
            return 0;
        int len = s.size();
        vector<int> dp(len + 1, 1);
        if (len == 1)
            return stoi(s) == 0 ? 0 : 1;
        for (int i = 2; i <= len; ++i)
        {
            int num = stoi(s.substr(i - 2, 2));
            if (num <= 26&&num >= 11&&num!=20)
            {
                dp[i] = dp[i - 2] + dp[i - 1];
            }
            else if (num % 10 == 0)
            {
                if (num == 10 || num == 20)
                    dp[i] = dp[i - 2];
                else
                {
                    return 0;
                    break;
                }
            }
            else
                dp[i] = dp[i - 1];
        }
        return dp[len];
    }
};
#endif