原题链接：https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668

描述

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
我们把一个字符串编码成一串数字，再考虑逆向编译成字符串。 由于没有分隔符，数字编码成字母可能有多种编译结果，例如 11 既可以看做是两个'a' 也可以看做是一个 'k' 。但 10 只可能是 'j' ，因为 0 不能编译成任何结果。 现在给一串数字，返回有多少种可能的译码结果

思路

容易看出翻译数字存在两种情况：只翻译一位或翻译两位，对于只翻译一位的情况，如果存在0，则无法单独翻译；那么对于翻译两位的情况，当第一位为0时无法翻译。
接着从整体视角来看：如果存在0，那么它的前面必须是1或2，否则无法翻译，直接返回0。
然后我们先从简单情况考虑，如2221，容易看到可以以2 2 2 1翻译，对于前两位可以组成22翻译，即22 2 1；
对于第二、第三位也可以组成22翻译，即XX 22 2 1；对于第三、第四位可以组成21翻译，即XXX 21。
那么我们可以发现：首先可以确定一种最细翻译方式，接着从第三位开始组合前两位检查它们是否能够被翻译，如果能翻译，那么就可以将前两位作为一组进行翻译，便将dp[i]=dp[i-1]+dp[i-2]，否则dp[i]=dp[i-1]。

代码

function solve(nums) {
  if (nums == "0") {
    // nums为0时直接返回0
    return 0;
  }
  if (nums == "10" || nums == "20") {
    // nums为10或20时只有1种翻译方式
    return 1;
  }
  // 先遍历一遍判断有0的地方前面是不是1或2，如果不是1或2则无法翻译，返回0
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] == "0") if (nums[i - 1] != "1" && nums[i - 1] != "2") return 0;
  }
  // 初始化dp数组
  let dp = new Array(nums.length + 1);
  dp[0] = dp[1] = 1;

  for (let i = 2; i <= nums.length; i++) {
    if (
      // 11-19||21-26时dp[i]=dp[i-1]+dp[i-2]
      (nums[i - 2] == "1" && nums[i - 1] != "0") ||
      (nums[i - 2] == "2" && nums[i - 1] > 0 && nums[i - 1] < 7)
    )
      dp[i] = dp[i - 1] + dp[i - 2];
    else dp[i] = dp[i - 1];
  }
  return dp[nums.length];
}

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/152.html
最后修改时间：2022-04-25 17:27:08
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！