题目描述

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

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

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

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

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

样例

输入："12258"

输出：5

算法

(动态规划) $O(n)$

状态表示：$f[i]$，表示将前 $i$ 个数字翻译成字符串的方案数
状态计算

1. 将当前数字翻译成单个字母，此时 $f[i]$ 等于将前 $i - 1$ 个数字翻译成字符串的方案数，f[i] = f[i - 1]
2. 将前一个数字和当前数字翻译成一个字母，此时 $f[i]$ 等于将前 $i - 2$ 个数字翻译成字符串的方案数，f[i] = f[i - 2]

边界

1. f[0] = 1，0 个数字方案数为 1，可以通过 $f[1]$ 推出，1 个数字的翻译方式只有一种（将当前数字翻译成单个字母），所以由 f[i] = f[i - 1] 知 f[0] = 1
2. $f[n]$ 就是答案

注意：枚举字符串时 i 从 1 开始，所以下标应该往前移一位，即第 i 个字符 s[i - 1]

时间复杂度

整个字符串被遍历一次，所以时间复杂度为 $O(n)$

C++ 代码

class Solution {
public:
    int getTranslationCount(string s) {
        int n = s.size();
        vector<int> f(n + 1);

        f[0] = 1;
        for (int i = 1; i <= n; i ++ )
        {
            f[i] = f[i - 1];
            // s[i - 1] 为当前数字，s[i - 2] 为前一个数字
            int num = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (i >= 2 && num >= 10 && num <= 25) f[i] += f[i - 2];
        }

        return f[n];
    }
};