跟着姚桑学算法-把数字翻译成字符串

题. 把数字翻译成字符串

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

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

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

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

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

数据范围
输入数字位数 [1,101]。

样例

输入："12258"

输出：5

【题解】--- 动态规划

类比爬楼梯，dp[n] = dp[n-1]+dp[n-2] ,dp[n]代表走到最后一个字符，有多少种翻译方法。
对于访问到当前的字符dp[n]，能有多少种翻译？

1. 当前字符翻译为1个字符这是一种方法，dp[n] = dp[n-1] ；
2. 当前字符和前一个字符共同翻译为一种方法 dp[n]+=dp[n-2]，此时的条件为前后两个字符可以翻译为同一个字符。以及 04,05,06，只能翻译为1种，其组合并不能作为一种翻译。

复杂度分析：

本题动态规划问题，时间复杂度为O(n)。

C++代码实现：

class Solution {
public:
    int getTranslationCount(string s) {
        if(s.empty()) return 0;
        int len = s.size();
        int dp[len+1];
        memset(dp,0,sizeof(dp));
        dp[0] = 1;
        dp[1] = 1;
        for (int i=2;i<=len;i++){
            dp[i] = dp[i-1];
            int  k = s[i-1] - '0';
            int k1 = s[i-2] - '0';
            if (k1 * 10 + k <= 25 && k1 != 0){
                dp[i]  += dp[i-2];
            }
        }
        return dp[len];
    }
};