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

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

提示：

  • 0 <= num < 231

方法

递归

方法1

定义递归函数

  • dfs 函数求：「当前指针位置到末尾的数字」的翻译方法数。
  • 节点的状态用指针表示，dfs 入口传 0。
  • 如果 指针 和 指针+1 对应的两位数在[10,25]内，则可以直译，有两种选择：
    • 翻译 1 个数，指针走一步，递归调用，返回出剩余数字的翻译方法数。
    • 翻译 2 个数，指针走两步，递归调用，返回出剩余数字的翻译方法数。
    • 二者相加，就是当前数字串的翻译方法数。

  • 如果 指针 和 指针+1 对应的两位数不在[10, 25]内，则无法直译，只有一个选择：

    • 翻译 1 个数，指针走一步，递归调用 dfs，返回出剩余子串的翻译方法数。 ```javascript const translateNum = (num) => { const str = num.toString();

    const dfs = (str, pointer) => { // 随着dfs向下，pointer右移 if (pointer >= str.length - 1) return 1; // 指针抵达边界和超出边界都返回1

    const temp = Number(str[pointer] + str[pointer + 1]); // 考察该2位数

    if (temp >= 10 && temp <= 25) { 

    1. return dfs(str, pointer + 1) + dfs(str, pointer + 2); // 2个分支的结果相加

    } else { 

    1. return dfs(str, pointer + 1);          // 返回1个分支的结果

    } }

    return dfs(str, 0); }

    1. <a name="OKnSY"></a>
    2. ### 方法2：记忆化递归
    3. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/355497/1650357809754-3197ca90-fb4e-43bc-b1df-673b133dd998.png#clientId=u2515eb95-3cc6-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=245&id=u43123ff9&margin=%5Bobject%20Object%5D&name=image.png&originHeight=738&originWidth=1507&originalType=binary&ratio=1&rotation=0&showTitle=false&size=200319&status=done&style=none&taskId=ud870b557-2023-43d1-b95a-65dc6ee4b6e&title=&width=500)
    4. ```javascript
    5. const translateNum = (num) => {
    6. const str = num.toString();
    7. const n = str.length;
    9. const memo = new Array(n);
    10. memo[n - 1] = 1;   // 指针临界时的子树的计算结果
    11. memo[n] = 1;       // 指针越界时的子树的计算结果
    13. const dfs = (str, pointer, memo) => {
    14.   if (memo[pointer]) return memo[pointer]; // 之前存过，直接拿来用
    16.   const temp = Number(str[pointer] + str[pointer + 1]);
    18.   if (temp >= 10 && temp <= 25) {
    19.     memo[pointer] = dfs(str, pointer + 1, memo) + dfs(str, pointer + 2, memo);
    20.   } else {
    21.     memo[pointer] = dfs(str, pointer + 1, memo);
    22.   }
    24.   return memo[pointer]; // 当前子树的计算结果向上返回
    25. };
    27. return dfs(str, 0, memo);
    28. }

    方法3：递归

    一、递归五部曲：
    1.dp数组的定义
    2.确定状态转移方程（遇到复杂一点的注意分情况讨论，其实主要就是找 dp[i],dp[i-1]…的关系，当然dp数组也可能是二维的
    3.确定遍历顺序
    4.dp数组初始化
    5.打印dp数组，检查值是否符合预期

    1. /**
    2. * @param {number} num
    3. * @return {number}
    4. */
    5. let translateNum=(num)=>{
    6.   let nums=num.toString()
    7.   let n =nums.length
    8.   let dp=new Array(n)
    9.   dp[0]=1
    10.   for(var i=1;i<n;i++){
    11.       if(nums[i-1]=='2'&&nums[i]<'6'){
    12.           dp[i]=dp[i-1]+(i>2?dp[i-2]:1)
    13.       }
    14.       else if(nums[i-1]=='1'){
    15.           dp[i]=dp[i-1]+(i>2?dp[i-2]:1)
    16.       }else{
    17.           dp[i]=dp[i-1]
    18.       }
    19.   }
    20.   return dp[n-1]
    21. }

    ⭐️方法4：

    算法
    一、f(n) = f(n-1) + f(n-2）
    二、数字先转换成字符串
    三、dp[]设置初始值

  • dp[0] = 1

  • dp[1] = 1

四、循环。计算numStr[i-2] * 10 + numStr[i-1]，

  • 如果在10~25之间， dp[i] 是前两种方案之和
  • 如果不是，则dp[i-1]的解法就是dp[i]的解法
    1. /**
    2. * @param {number} num
    3. * @return {number}
    4. */
    5. var translateNum = function(num) {
    6. const numStr = `${num}`;
    7. let len = numStr.length;
    8. let dp = new Array(len + 1)
    9. dp[0] = 1;
    10. dp[1] = 1;
    11. for (let i = 2; i <= len; i++) {
    12.   let n = (numStr[i-2] -'0') * 10 + (numStr[i-1] - '0');
    13.   if (n >= 10 && n <= 25) {
    14.     dp[i] = dp[i-1] + dp[i-2]
    15.   } else {
    16.     dp[i] = dp[i-1]
    17.   }
    18. }
    19. return dp[len]
    20. };

    20220419： 执行用时：52 ms, 在所有 JavaScript 提交中击败了95.15%的用户 内存消耗：41 MB, 在所有 JavaScript 提交中击败了65.12%的用户 通过测试用例：49 / 49

动态规划

方法1

动态规划和递归的区别
递归不断压栈再不断出栈，是自上而下解决问题，等待下面返回上来的结果。动态规划是自下而上解决问题，从已知的case出发，存储前面的状态，迭代出最后的结果。动态规划就是想办法不用递归，利用递推关系用“填表格”的方式顺序计算。每个dp项的值其实等于一个递归子调用的结果（递归子问题的解）。
思路
其实这题就是一道青蛙跳台阶，只不过在一次性跳两阶时，要判断条件，不符合就不准跳两阶
回到这题，要判断的条件是 两位数是否大于9且小于26
对于动态规划方程：
dp[i] 表示 前 i 位 可以解码的总数
分两种情况：

  1. 第 i 位数字 无法和前面的数组合，

比如 1245, 5 只能单独翻译，那么方法数和 124 是一样的
dp[i] = dp[i - 1]

  1. 第 i 位数字 可以和前面的数组合，

比如 1215, 5 可以选择 组合 和 不组合，最终结果为两种情况相加
a. 选择组合，15看成是整体，那么 dp[i] = dp[i - 2]
b. 不选择组合，5单独翻译，那么 dp[i] = dp[i - 1]
所以 dp方程如下

  • dp[i] = dp[i - 1]，第 i 位数字 无法和第 i - 1 位数字组合
  • dp[i] = dp[i - 1] + dp[i - 2]，第 i 位数字可以和第 i - 1 位数字组合

明确好动态规划方程和条件时，回到如何从原数字中截取每一位或每两位数字出来进行判断

  1. 原数字 + ‘’：将数字转换为字符串，每次取两位字符进行判断即可，只不过判断时注意要将 这两位字符 * 1 才能转换为数字进行判断
  2. 原数字不断跟100取余，通过余数来判断，因为100的余数就是这两位数字了，由于循环是每次 num / 10，所以可以保证每次缩小一位，在这基础上判断跟100的余数，满足“从原数字中截取每一位或每两位数字出来进行判断”的条件
    1. var translateNum = function(num) {
    2.  let i, dp = [1];
    3.  for(i = 1; num > 0; i++, num = Math.floor(num / 10)) {
    4.      if(num % 100 > 9 && num % 100 < 26) {
    5.          if(i === 1) {
    6.              dp[i] = 2;
    7.          } else {
    8.              dp[i] = dp[i - 1] + dp[i - 2];
    9.          }
    10.      } else {
    11.          dp[i] = dp[i - 1];
    12.      }
    13.  }
    14.  return dp[i - 1];
    15. };

    方法3：区间动态规划 / 滚动数组

    一、滚动数组是一种常见的空间优化
    二、整个数字的翻译结果数= 除去最后1位的部分的翻译结果数 1 + 除去最后2位的部分的翻译结果数 * 1
    f(n) = f(n-1) + f(n-2) ，及r = p + q
  • 定义状态：dp[i]表示nums[0…i]能翻译成字符串的种类数
  • 状态转移方程：dp[i] = dp[i-1] + dp[i-2]（如果nums[(i-1)…i]可以翻译）
  • 初始化：dp[0] = 1(0-9各自可以翻译成1种结果）
  • 输出：dp[len-1]
  • 思考空间优化：当前状态只与前两个状态相关，因此可以使用「滚动变量」，使用的空间与问题规模无关。

算法
一、f(n) = f(n-1) + f(n - 2)
二、dp[0]

  • i = 0时，p = 0, q = 0, r = 1，返回的结果为1

二、循环

  • p = q
  • q = r
  • 中间加判断 i为0时跳出此次循环

  • 判断[i-1, i+1)是否在10~25之间，如果是r = p + q ;

    1. var translateNum = function(num) {
    2. let str = `${num}`;
    3. let p = 0, q = 0, r = 1;
    4. for (let i = 0; i < str.length; i++) {
    5.   p = q;
    6.   q = r;
    7.   if (i === 0) {
    8.     continue;
    9.   }
    11.   let pre = str.substring(i -1, i+1);
    12.   if (~~pre >= 10 && ~~pre <= 25) {
    13.     r = p + q;
    14.   }
    15. }
    16. return r;
    17. };

    20220419： 执行用时：60 ms, 在所有 JavaScript 提交中击败了67.01%的用户 内存消耗：40.7 MB, 在所有 JavaScript 提交中击败了84.41%的用户 通过测试用例：49 / 49

复杂度分析

  • 时间复杂度：循环的次数是 n 的位数，故渐进时间复杂度为 O(log⁡n)。
  • 空间复杂度：虽然这里用了滚动数组，动态规划部分的空间代价是 O(1)的，但是这里用了一个临时变量把数字转化成了字符串，故渐进空间复杂度也是 O(log⁡n)。