剑指Offer题解 - Day21

「剑指 Offer 46. 把数字翻译成字符串」

力扣题目链接

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

示例 1:

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

「提示：」

• 0 <= num < 2^31

思路：

此题可以使用动态规划进行求解。首先，我们需要找到动态规划方程：

• 首先定义dp[i]表示i位数字的解决方案。
• 如果第i位的数字和第i - 1位的数字可以组合并翻译为字符串。那么，dp[i] = dp[i - 1] + dp[i - 2] 。原因是最后两位数字既可以组合，也可以拆开单独翻译。也就是说，当拆开的时候，就是dp[i - 1]的数量；当合并的时候，就是dp[i - 2]的数量，因此两者相加就是dp[i]
• 如果第i位的数字和第i - 1位的数字不能组合。那么，dp[i] = dp[i - 1]。
• 最后，需要找出动态规划的初始值。可得：dp[0] = dp[1] = 1。也就是说，0个数字和1个数字只有一种翻译方法。

找到了动态规划方程，接下来需要考虑如何写代码。先上代码：

动态规划

/**
 * @param {number} num
 * @return {number}
 */
var translateNum = function(num) {
    let s = String(num);
    let a = 1;
    let b = 1;
    for (let i = 2; i <= s.length; i++) {
        let temp = s.slice(i - 2, i);
        let c = (temp >= '10') && (temp <= '25') ? a + b : a;
        b = a;
        a = c;
    }
    return a;
};

• 「时间复杂度 O(n)」。
• 「空间复杂度 O(n)」。

分析：

为了方便进行遍历，这里首先将数字转换为字符串进行处理。分别初始化dp[0]和dp[1]的值，全部为1。

然后进行循环字符串。注意这里的循环条件，这样处理是因为：我们需要截取字符串中的两位用来判断是否可以组合。由于slice方法是左闭右开区间，因此我们从第三位，也就是索引为2处开始遍历。而终止条件是 i≤ s.length ，同样是因为左闭右开。

接下来将截取的字符串用来比较。如果两位字符既可以组合，也可以拆开。也就是说范围是[10,25] ，此时满足dp[i] = dp[i - 1] + dp[i - 2] ，所以执行c = a + b ，如果不可以组合，满足dp[i] = dp[i - 1] ，执行c = a 。

由于dp[i]只和前面两个数字有关系，因此这里通过维护额外的变量来保存。通过变量的交替前进，最终的结果是变量a保存的值，返回a即可。

复杂度方面，时间复杂度是字符串的遍历次数；空间复杂度是转换为字符串占用的额外空间。

总结

可以看作特殊的跳台阶问题，每个台阶上都有个数字。特殊性就在于，跳台阶问题是可以随意选择跳一个还是跳两个，而这道题想跳两个就必须满足一个条件，即要跳的两个台阶上的数字组成的十进制数在10-25之间时，才可以跳。