剑指offer - 把数字翻译成字符串 - JavaScript

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

# 解法:回溯法

这题其实就是求解空间树中,从定点到叶节点的路径总数。需要注意的是,每次可以选择 1 位数字,或者合法的 2 位数字(10 <= n <= 25)。

以 123 为例,它的解空间树如下:

可以看到,从图中可以看到,一共有三种合法的翻译方式:

  • 1、23
  • 1、2、3
  • 12、3

代码实现如下:

// ac地址: https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
// 原文地址:https://xxoo521.com/2020-03-10-num-to-str/

/**
 * @param {number} num
 * @return {number}
 */
var translateNum = function (num) {
  let result = 0;
  traceback(num + "", 0);
  return result;

  /**
   * @param {string} str
   * @param {number} start
   */
  function traceback(str, start) {
    if (start >= str.length) {
      ++result;
      return;
    }

    traceback(str, start + 1);
    const sub = str.substr(start, 2);
    if (sub.length === 2 && sub >= "10" && sub <= "25") {
      traceback(str, start + 2);
    }
  }
};

# 更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇