微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 46.把数字翻译成字符串

剑指offer 46.把数字翻译成字符串

题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：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];
    }
};

Java 代码

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i ++ ) {
            f[i] = f[i - 1];
            if (i >= 2) {
                int val = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
                if (val >= 10 && val <= 25) {
                    f[i] += f[i - 2];
                }
            }
        }
        return f[n];
    }
}

Python 代码

class Solution:
    def translateNum(self, num):
        s = str(num)
        n = len(s)
        f = [0] * (n + 1)
        f[0] = 1
        for i in range(1, n + 1):
            f[i] = f[i - 1]
            if i >= 2:
                val = int(s[i - 2:i])
                if 10 <= val <= 25:
                    f[i] += f[i - 2]
        return f[n]

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer