题目描述

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

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

一个数字可能有多个翻译。例如12258有5种不同的翻译，它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。

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

样例

输入："12258"

输出：5

LeetCode 传送门：Decode Ways

Leetcode里面的题和这一题有一点点区别（LeetCode里面是从1编码到26，LeetCode里0是非法字符！！）

本题解法

DP $O(N)$

还记得经典的爬楼梯(斐波那契数列)吗？每次可以走1步或者2步，问n个台阶一共有多少种爬楼梯的方法？
dp[i]=dp[i-1]+dp[i-2]

这道题相当于加了一些限制条件。

这个题可以正推或者倒推，我采用的方法是倒着推

以dp[i]表示从字符串i位开始到末尾，最大的翻译次数。

dp[i] = dp[i+1] // default, 比如都是67876878，这种只有1种解码方式，不会增加 = dp[i+1] + dp[i+2] // when s[i]=='1'||(s[i]=='2'&&s[i+1]<'6') 这种情况的出现会使解码次数增加
举个例子12xxxxxx;将1作为单独的一个数看，解码方法和2xxxxxx相同
；将12作为一个整体看，解码方法数量和xxxxxx相同。
最终的数量是二者之和。

C++ 代码

/**
 * 1268
 * 1 2 6 8
 * 1 26 8
 * 12 6 8
 * 
 */
class Solution {
public:
    int getTranslationCount(string s) {
        int n = s.size();
        if(!n) return 0;
        if(n==1) return 1;

        vector<int> dp(n+1, 0);
        dp[n-1] = 1;
        for(int i=n-2;i>=0;i--){
            dp[i] = dp[i+1];
            if(s[i]=='1' || (s[i]=='2' && s[i+1]<'6')){
                dp[i] += dp[i+2];
            }
        }
        return dp[0];
    }
};

由于只涉及到往前2位的状态，也可以将空间复杂度优化到$O(1)$

LeetCode题

DP $O(N)$

时间复杂度是一样的，问题就在0字符非法。
以dp[i]表示从字符串i位开始到末尾，最大的翻译次数。
遇到0字符，令dp[i]=0
否则，处理方法和本OJ中的类似，
dp[i] = dp[i+1] = dp[i+1] + dp[i+2] // when s[i]=='1'||(s[i]=='2'&&s[i+1]<='6')
一定要注意是<='6'，我擦坑了好久。。。

C++ 代码

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        if(!n) return 0;
        if(n==1) return s[0]=='0'?0:1;
        vector<int> dp(n+1, 0);
        dp[n]=1;
        for(int i=n-1;i>=0;i--){
            if(s[i]=='0') dp[i]=0;
            else{
                dp[i]=dp[i+1];
                if(i<n-1 && s[i]=='1' || (s[i]=='2' && s[i+1]<='6'))
                    dp[i]+=dp[i+2];
            }
        }
        return dp[0];
    }
};