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