回溯
解题思路
获取所有解，首先想到的就是回溯，首先使用 数组 存储每个数字对应的所有可能的字母，然后进行回溯操作；
回溯过程中维护一个 path 数组，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）：
- 该 path 数组初始为空，每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面；
- 然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列；
然后进行回退操作，遍历其余的字母排列；
图解
代码实现
var letterCombinations = function (digits) {
let res = [];
let len = digits.length; //要匹配的结果长度
// 按键对应的字母
const phoneArrMap = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
if (len === 0) return res;
if (len === 1) return phoneArrMap[digits].split('');
backtrack(res, phoneArrMap, digits, 0, []);
return res;
};
/**
* @param {*} res 结果
* @param {*} phoneArrMap 键盘映射
* @param {*} digits 按键字符串组合
* @param {*} startInx 开始索引
* @param {*} path 结果路径
* @returns
*/
const backtrack = (res, phoneArrMap, digits, startInx, path) => {
if (path.length === digits.length) {
res.push(path.join(''));
return;
}
for (const v of phoneArrMap[digits[startInx]]) {
path.push(v);
backtrack(res, phoneArrMap, digits, startInx + 1, path);
path.pop();
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 47. 全排列 II
上一篇
评论
