Open
Description
方法一：回溯法（DFS）
解题思想：
代码：
var letterCombinations = function (digits) {
if (digits.length == 0) return [];
const map = new Map(),
res = [];
// 初始化字典映射
map.set("2", "abc");
map.set("3", "def");
map.set("4", "ghi");
map.set("5", "jkl");
map.set("6", "mno");
map.set("7", "pqrs");
map.set("8", "tuv");
map.set("9", "wxyz");
const dfs = (curStr, i) => {
// 指针越界，递归的出口
if (i > digits.length - 1) {
// 将解推入res
res.push(curStr);
// 结束当前递归分支，进入另一个递归分支
return;
}
const letters = map.get(digits[i]);
// 不同的字母选择代表不同的递归分支
for (const l of letters) {
dfs(curStr + l, i + 1);
}
};
dfs("", 0);
return res;
};复杂度分析：
- 时间复杂度：遍历所有节点，最坏的情况去到 O(4^n)，n 为数字串的长度。
- 空间复杂度：O(n)，递归栈调用的深度。
方法二：BFS
解题思想：
维护一个队列。
起初让空字符串入列，让当前层的字符串逐个出列，出列的字符串，会构建它下一层的新字母串，并入列。
一层层地，考察到数字串的最末位，就到了最底一层，此时队列中存的是所有构建完毕的字母串，返回 queue 即可。
和传统的BFS不同，这里控制了层序遍历的深度，等于 digits 的长度，而不是 while(queue.length){.. 那样让所有的节点入列出列，最后还会剩下最后一层节点，留在 queue 中返回。
代码：
const letterCombinations = (digits) => {
if (digits.length == 0) return [];
const map = {
2: "abc",
3: "def",
4: "ghi",
5: "jkl",
6: "mno",
7: "pqrs",
8: "tuv",
9: "wxyz",
};
const queue = [];
queue.push("");
for (let i = 0; i < digits.length; i++) {
// bfs的层数，即digits的长度
const levelSize = queue.length; // 当前层的节点个数
for (let j = 0; j < levelSize; j++) {
// 逐个让当前层的节点出列
const curStr = queue.shift(); // 出列
const letters = map[digits[i]];
for (const l of letters) {
queue.push(curStr + l); // 生成新的字母串入列
}
}
}
return queue; // 队列中全是最后一层生成的字母串
};复杂度分析：