剑指 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之间时，才可以跳。
作者：chuck
链接：https://juejin.cn/post/7061968854527770655