深度优先搜索(DFS)---递归实现
程序员文章站
2022-06-11 12:37:11
...
题目描述
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
输入:“23”
输出:[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
说明:
尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
我的思路
可以用递归来解题,对输入的键位进行,解析出每个键位对应的字母ascii码进行循环遍历,深度优先遍历,输入的键位数即层数,当前层数对应的字母遍历完以后即回溯至上一层,当递归深度为键位数的时候即获得一种结果。
我的代码
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
var result = [];
recursion(result,digits,0,'');
return result;
};
var recursion = function(result,digits,digitIndex,currStr){
//边界条件
if(digitIndex>=digits.length){
return;
}
// 获取对应键位的字母集
const digit = digits[digitIndex];
let codeStart = 97+(digit-2)*3;
let codeEnd = codeStart+2;
if(digit==='8'||digit==='9'){
codeStart+=1;
if(digit==='8'){
codeEnd+=1;
}
}
if(digit==='7'|| digit==='9'){
codeEnd = codeStart+3;
}
for(let code=codeStart;code<=codeEnd;code++){
const str = currStr+String.fromCharCode(code);
if(digitIndex===digits.length-1){
result.push(str);
}else{
recursion(result,digits,digitIndex+1,str);
}
}
}
上一篇: 1131 Subway Map