[路飞]_17. 电话号码的字母组合

站长
· 阅读数 3
「这是我参与2022首次更文挑战的第28天,活动详情查看:2022首次更文挑战」
题目
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例1
输入: digits = "23"
输出: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
实例2
输入: digits = "2"
输出: ["a","b","c"]
题解
全排列思想: 递归 + 回溯
首先肯定是要先将参数转换为字符串;构建一个哈希表将数字与字母关系一一对应: map={2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz,}map = \{ 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz, \}map={2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz,}
得到数字与字母关系一一对应
举个例子:digits="23" digits = "23"digits="23",对应的字符串可以表示为 list=[abc,def]list = [abc,def]list=[abc,def]
返回所有它能表示的字母组合,是不是就是 list 数组中所有字符串全排列组合呀?
按照全排列思想,递归 + 回溯
一定可以解决问题的
如何递归?
const len = list.length
// 开始递归
dfs(0, []);
// idx : 表示list中下标
function dfs(idx, path) {
// 最终组成的字符串长度一定等于 list,并且这也是递归的终止条件
if (path.length === len) {
return;
}
for (let i = 0; i < (3||4); i++) {
// (3||4):或者是3或者是4,因为数字7表示字母pqrs,有4位,所以i可能小于3或者小于4,是动态的;
// 这里就体现 idx 的价值了,idx表示list中下标,i < (3||4); 可以修改为 i < list[idx].length
}
}
如何回溯?
for (let i = 0; i < list[idx].length; i++) {
const s = list[idx][i];
//符合条件字母的添加到路径上保存
path.push(s);
// 递归下一步
dfs(idx + 1, path);
// 回溯,递归结束后删除
path.pop();
}
路径保存字母为什么使用数组?因为回溯的时候操作数组比操作字符串方便
根据上述思路编辑代码如下:
完整代码
const map = {
2: 'abc',
3: 'def',
4: 'ghi',
5: 'jkl',
6: 'mno',
7: 'pqrs',
8: 'tuv',
9: 'wxyz',
};
var letterCombinations = function (digits) {
const len = digits.length;
if (len === 0) return [];
const list = [];
for (let i = 0; i < len; i++) {
const k = digits[i];
list.push(map[k]);
}
const result = [];
dfs(0, []);
return result;
function dfs(idx, path) {
if (path.length === len) {
const t = path.join('');
result.push(t);
return;
}
for (let i = 0; i < list[idx].length; i++) {
const s = list[idx][i];
path.push(s);
dfs(idx + 1, path);
path.pop();
}
}
};