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

网站建设与推广协议seo自学教程seo免费教程

news 2025/7/16 7:30:23

网站建设与推广协议,seo自学教程seo免费教程,网站查询访问域名,flash 做ppt的模板下载网站算法名称电话号码的字符组合算法描述给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。示例 1： 输入&…

算法名称

电话号码的字符组合

算法描述

给定一个仅包含数字 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;
};