给定一个数字，我们按照如下规则把它翻译为字符串：

0 翻译成 a，1 翻译成 b，……， 11 翻译成 l，……，25 翻译成 z。

一个数字可能有多个翻译。

例如 12258 有 5 种不同的翻译，它们分别是 bccfi、bwfi、bczi、mcfi 和 mzi。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

样例

1
2
3

输入："12258"

输出：5

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    int getTranslationCount(string s) {
        int val=0;
        int n = s.size();
        if(n==0) return 0;
        
        vector<int> dp(n+1);
        dp[0] = 1;
        for(int i=1;i<=n;++i) {
            val = s[i-1] -'0';
            if(val>=0 && val<=9) {
                if(i) dp[i] += dp[i-1];
            }
            if(  i-2>=0) {
                int pre = s[i-2] -'0';
                if(pre==0) {
                    //有前导0，不能算数
                    continue;
                }
                val = pre *10 + val;
                if(val > 0 && val<=25)
                    dp[i] += dp[i-2];
            }
        }
        return dp[n ];
    }
};