题目描述

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

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

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

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

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

样例
输入：”12258”

输出：5

算法1

(dfs) $O(n^2)$

C++ 代码

class Solution {
public:
    int n = 0, res = 0;
    int getTranslationCount(string s) {
        n = s.size();
        dfs(s,0);
        return res;
    }

    void dfs(string &s, int u){
        if(u == n){
            ++res;
            return;
        }

        int num = 0;
        for(int i = 0; i < 2 && u + i < n; ++i){
            int tmp = num;
            num = num * 10 + s[u + i] - '0';
            if(tmp==0 && i==1) continue; //会出现 04 01 02 这样的组合，但是这样的组合不符合规则。
                                        //05 这样的数，去掉，还可以if（i == 1 && num <10）
            if(num < 26){                
                dfs(s, u + 1 + i);
            }
        }
    }
};

算法2

(DP) $O(n)$

C++ 代码

class Solution {
public:
    int getTranslationCount(string s) {
        //状态划分  前i个数字的所有翻译方式
        int n = s.size();
        vector<int> f(n + 1, 0);
        f[0] = 1;
        f[1] = 1;
        for(int i = 2; i <= n; ++i){  //保证不越界
            f[i] = f[i - 1];
            int num = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if(num >=10 && num <=25) f[i] =f[i - 1] + f[i - 2];
        }
        return f[n];
    }
};