电话号码的字母组合
难度：中等 来源：17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
思路：
- 一看到题目里提到的任意组合就应该立刻想到使用回溯算法；
- 回溯算法的核心就是第一要找到路径，第二要选择列表，第三要知道结束条件是什么。
- 理解了以上这3点，然后就很好的应用到实际例子里了，比如这题里路径就是字符组合，而列表就是递归树的分支，然后结束条件就是字符的长度。
题解：
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
if (digits.length === 0) return []
const map = {
2: 'abc',
3: 'def',
4: 'ghi',
5: 'jkl',
6: 'mno',
7: 'pqrs',
8: 'tuv',
9: 'wxyz'
}
let res = []
const dfs = (curStr, index) => {
if (index > digits.length - 1) {
res.push(curStr)
return
}
let letters = map[digits[index]]
for (let l of letters) {
dfs( curStr + l, index + 1)
}
}
dfs('', 0)
return res
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-01-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
