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

简介: 电话号码的字符组合

算法名称

电话号码的字符组合

算法描述

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

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

4a4826fac41142d88feb24b409bfc5d2.png

示例 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”]。

025b3519f3114a88925cc01ede77d535.jpg

算法解析代码

var letterCombinations = function(digits) {
  //获取digits的长度
    const k = digits.length;
    //使用map
    const 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;
};

算法只有多写多练,我们的算法逻辑和能力才能获得提高,继续fighting✨✨✨

期待获得你们的支持,有更好的想法欢迎评论指出💖💖💖



目录
相关文章
|
2月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
48 0
|
7月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-439 算法训练 简单字符变换
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-439 算法训练 简单字符变换
55 1
|
7月前
|
算法
LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)
LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)
63 0
|
4月前
|
算法
【算法】位运算算法——判断字符是否唯一
【算法】位运算算法——判断字符是否唯一
|
4月前
|
算法
【算法】滑动窗口——无重复字符的最长子串
【算法】滑动窗口——无重复字符的最长子串
|
5月前
|
自然语言处理 Rust 算法
【算法】17. 电话号码的字母组合(多语言实现)
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
【算法】17. 电话号码的字母组合(多语言实现)
|
7月前
|
算法 测试技术 编译器
【算法 | 实验18】在字符矩阵中查找给定字符串的所有匹配项
题目描述 题目 在字符矩阵中查找给定字符串的所有匹配项 给定一个M×N字符矩阵,以及一个字符串S,找到在矩阵中所有可能的连续字符组成的S的次数。所谓的连续字符,是指一个字符可以和位于其上下左右,左上左下,右上右下8个方向的字符组成字符串。用回溯法求解。
107 1
|
7月前
|
算法 C++
【优选算法】——滑动窗口——3. 无重复字符的最长子串
【优选算法】——滑动窗口——3. 无重复字符的最长子串
|
6月前
|
算法
数据结构和算法——散列函数的构造方法(直接定址法、除留余数法、数字分析法、折叠法、平方取中法、ASCII码加和法、前三字符移位法)
数据结构和算法——散列函数的构造方法(直接定址法、除留余数法、数字分析法、折叠法、平方取中法、ASCII码加和法、前三字符移位法)
68 0
|
7月前
|
人工智能 算法 测试技术
【字符串】【C++算法】828.统计子串中的唯一字符
【字符串】【C++算法】828.统计子串中的唯一字符