原题链接:leetcode-cn.com/problems/le…
解题思路:
- 可以先参考题解回溯+队列 图解中队列部分的动画。
- 如果输入为
23
,假设在队列已存储了2
的组合['a', 'b', 'c']
,要生成23
的组合,只需要将当前队列逐个出队,每个元素都合并3
对应的字母映射,再重新入队即可。 - 经过步骤2后,队列中即为为
23
的所有可能组合,只要将其作为结果返回即可。 - 队列的初始状态为
['']
,将空数组作为初始值,可以用来生成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;
};
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!