写点什么

LeetCode 题解:17. 电话号码的字母组合,队列,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 11 月 27 日
LeetCode题解:17. 电话号码的字母组合,队列,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/


解题思路:


  1. 可以先参考题解回溯+队列 图解中队列部分的动画。

  2. 如果输入为23,假设在队列已存储了2的组合['a', 'b', 'c'],要生成23的组合,只需要将当前队列逐个出队,每个元素都合并3对应的字母映射,再重新入队即可。

  3. 经过步骤 2 后,队列中即为为23的所有可能组合,只要将其作为结果返回即可。

  4. 队列的初始状态为[''],将空数组作为初始值,可以用来生成2对应的组合['a', 'b', 'c']


/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function (digits) {
// 如果传入digits为空,则直接返回结果[]
if (!digits || !digits.length) {
return [];
}
// 使用Map存储按键对应的字母
const map = new Map([
['2', 'abc'],
['3', 'def'],
['4', 'ghi'],
['5', 'jkl'],
['6', 'mno'],
['7', 'pqrs'],
['8', 'tuv'],
['9', 'wxyz'],
]);
// 使用队列生成组合
// 队列存入一个空字符串作为初始值,用于生成第一个数字对应的字母映射
let queue = [''];
// 遍历数字,以此生成所有组合
for (let i = 0; i < digits.length; i++) {
// 获取当前数字对应的字母映射
const letters = map.get(digits[i]);
// 由于新生成的组合会重新入队,因此队列的长度是可变的
// 为保证新组合,都是在已有组合的基础上生成的
// 因此缓存当前队列的长度,用于将相应数量的组合出队。
let queueLength = queue.length;
// 每次循环都将上一次生成的组合出队,用于生成新组合
while (--queueLength >= 0) {
// 出队一个组合
const shiftItem = queue.shift();
// 将上一次的组合,与当前的字母映射逐个组成新组合
for (let j = 0; j < letters.length; j++) {
queue.push(shiftItem + letters[j]);
}
}
}
// 完成循环后,队列即为所有组合
return queue;
};
复制代码


发布于: 2020 年 11 月 27 日阅读数: 23
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:17. 电话号码的字母组合,队列,JavaScript,详细注释