17-电话号码的字母组合
标签：哈希表 字符串 回溯
题目信息
题目地址： 17-电话号码的字母组合
题目内容：
javascript
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
题解
解法一
思路：
将每个数字代表的字母写入map中，然后获取数字字符串对应的字母的二维数组，例如
12对应的二维数组是[['a', 'b', 'c'], ['d', 'e', 'f']]进行两轮循环，
第一轮循环是循环数字对应的二维数组
第二层循环会生成最新的字母组合，然后将将最新的组合数组和第一轮循环的当前项再次进行拼接
最终返回循环结果就行
代码实现：
javascript
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
if(!digits.length) return []
const numMap = new Map([
[2, 'abc'],
[3, 'def'],
[4, 'ghi'],
[5, 'jkl'],
[6, 'mno'],
[7, 'pqrs'],
[8, 'tuv'],
[9, 'wxyz'],
])
// 先生成所有字母的二维数组
const digitsArr = digits.split('').reduce((prev, cur) => {
prev.push(numMap.get(+cur).split(''))
return prev
}, [])
// 如果只有一个数字字符串那么就返回它对应的字母
if(digitsArr.length === 1) return digitsArr[0]
// 进行两层reduce循环
return digitsArr.reduce((prev, cur) => {
// 得到最新的组合数组prev
return prev.reduce((iPrev, iCur) => {
// 循环prev，将prev和后面的数字对应的字母进行组合
const genStrs = cur.map(j => `${iCur}${j}`)
return [...iPrev, ...genStrs]
}, [])
})
};
解法二
思路：
使用
回溯算法解决该问题
代码实现：
javascript
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
if(!digits.length) return [];
const numMap = new Map([
["2", "abc"],
["3", "def"],
["4", "ghi"],
["5", "jkl"],
["6", "mno"],
["7", "pqrs"],
["8", "tuv"],
["9", "wxyz"],
]);
const res = [];
// 先生成所有字母的二维数组
const backTracking = (path, curIndex, res) => {
if(path.length === digits.length) {
res.push(path.join(""));
return;
}
const choices = numMap.get(digits[curIndex]).split("");
for (const i of choices) {
path.push(i);
backTracking(path, curIndex + 1, res);
path.pop();
}
};
backTracking([], 0, res);
return res;
};