当前位置：首页 > news >正文

【算法】算法题解---电话号码的字符组合

news 2025/8/23 6:40:54

算法名称

电话号码的字符组合

算法描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
在这里插入图片描述
示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：

输入：digits = “”
输出：[]

示例 3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

算法分析

数字和字母的映射： 可以使用map或者定义一个二维数组，例如：string letterMap[10]，来做映射，我这里定义一个二维数组，代码如下：

const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9
};

用回溯法解决for循环：
从下图中可以看出遍历的深度，就是输入"23"的长度，而叶子节点就是我们要收集的结果，输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。

在这里插入图片描述

算法解析代码

var letterCombinations = function(digits) {//获取digits的长度const k = digits.length;//使用mapconst map = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"];//digits为空，则输出[]if(!k) return [];//当digits只有一个数字，则通过分割字符串的方式用map获得结果if(k === 1) return map[digits].split("");//定义函数function backtracking(n, k, a) {//当path的长度等于digits的长度，则匹配完毕，添加到res中if(path.length === k) {res.push(path.join(""));return;}//对digits相对应的数字所包含的字母进行递归添加到path中for(const v of map[n[a]]) {path.push(v);//进行递归backtracking(n, k, a + 1);path.pop();}}const res = [], path = [];//调用函数backtracking(digits, k, 0);//返回结果return res;
};