剑指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);
        }
    }
};

更多资料

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

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×