题目描述:给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
这题其实就是求解空间树中,从定点到叶节点的路径总数。需要注意的是,每次可以选择 1 位数字,或者合法的 2 位数字(10 <= n <= 25
)。
以 123 为例,它的解空间树如下:
可以看到,从图中可以看到,一共有三种合法的翻译方式:
代码实现如下:
// 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);
}
}
};