题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示：

• $0 <= num < 2^{31}$

---

算法

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

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

1. 将当前数字翻译成单个字母，此时 $f[i]$ 等于将前 $i - 1$ 个数字翻译成字符串的方案数，f[i] = f[i - 1]
2. 如果当前数字和前一个数字构成的两位数 $val$ 满足 $10 <= val <= 25$，则可以将前一个数字和当前数字翻译成一个字母，此时 $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)$

空间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num);
        int n = s.size();
        vector<int> f(n + 1);
        f[0] = 1;
        for (int i = 1; i <= n; i ++ ) {
            f[i] = f[i - 1];
            if (i >= 2) {
                int val = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
                if (val >= 10 && val <= 25)
                    f[i] += f[i - 2];
            }
        }
        return f[n];
    }
};