力扣 17 - 电话号码的字母组合【回溯、哈希映射、队列】

作者：Fire_Shield

2022 年 9 月 09 日
浙江
本文字数：6149 字
阅读完需：约 20 分钟

@TOC

题目描述及分析

力扣.17

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

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

示例 2：

输入：digits = "" 输出：[]

示例 3：

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

思路分析

以第一个为例,digits = "23"，表明从电话号码的按键中选取 2 和 3 这两个字符，然后去寻找它们各自所对应的字母，这里每一个数字字符所对应的字母的不同，0 对应的是空字符，而 1 的话题目中讲到是==不对应任何字母==，要注意的是像 7 和 9 所对应的是 4 个字母。
以上这些应该用一个数组或者容器将它们存起来，可以使用 map，二维数组，也可以使用哈希表，后面进行对应的读取即可
看这里的输出，是数字字符所对应的字母的组合，组合的个数恰好和给出的 digits 的个数时相同的，示例 1 是 2 个，示例 3 是 1 个，所以

解法一：dfs + map

分步讲解

首先，看到题目给出来的主函数接口，返回值类型是是一个多个字符串构成的集合

public:    vector<string> letterCombinations(string digits) {    }};

复制代码

因此我们需要先定义一个 result 去存放最终的结果，再定义一个 string 类型的字符串去收集每次所产生的的字母组合

 string s;               //存放每次的结果 vector<string> result;      //存放最后的结果

复制代码

接着，需要将每个数组所对应的字母集合拿一个容器存放起来，这里用 map 最合适不过，key 值的类型定义为 char，用来接收每个数字；value 值的类型定义为 string，用来接收每个数字所对应的字母集合

 map<char,string> table={     {'0'," "},{'1'," "},{'2',"abc"},{'3',"def"},     {'4',"ghi"},{'5',"jkl"},{'6',"mno"},     {'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}, };

复制代码

接着，就需要通过 DFS，去判断每一次的结果,首先我们观察它的参数，需要传入的是题目给出的数串 digits，以及此数串所代表的长度 index,这里不同于回溯算法的其他题目之处是，其他题目是通过一个==集合来求组合==，但这题是通过==多个集合求组合==，各个集合之间互不影响，因此不需要 startindex 这个变量来改变每次的访问起始位置，像我之前讲过的那道题 93.复原IP地址就需要每次替换起始位置，因为基于回溯的思想，因此需要遍历所有的结果和可能性，还有像这些题目，都需要用到 startindex 来改变每次回溯的起始位置，后续也会出相应讲解📕39.组合总和 78.子集 491.递增子序列
跳过终止条件，先来看后面的过程👇

void DFS(const string& digits,int index)    //①递归参数//digits:表示输入的数串       index:表示单个数串长{    //递归终止条件    if(index == digits.size())    {        result.push_back(s);        return;    }
    char num = digits[index];   //首先获取是数字键上的哪一个数字    string str = table[num];    //接着根据数字寻找对应的源字符串    
    for(int i=0;i<str.size();++i)       //通过不断回溯查询所有可能结果    {        s.push_back(str[i]);        DFS(digits,index+1);        s.pop_back();    }};

复制代码

① 首先，要先取到数字键上所对应的那个数字，也就是通过传入的 index 来访问，定义一个 char 类型的变量去接收一下；② 然后再根据找到的这个数字，去 map 中通过 key 值去找到对应的字母串③ 最后就是通过循环去遍历这个字母串，也是基于一个回溯的思想，遍历完一种可能的结果，就将其放入 s 中，就算是一种路径，然后接着递归和 pop_back 回溯具体遍历如图所示。👇

最后就是这个递归的终止条件，因为这个 startindex 每递归一次都是会增加一次，这个示例的长度为 2，因此递归 2 次即可，也就是 0 和 1，因为在主函数接口中我们传入的 startindex 是从 0 开始的，因此当它等于 digits.size()是，便终止递归然后将路径结果存放进 result 结果集中，接着 return
最后的话就是主函数接口里的一些参数初始化和结果的返回,s 和 result 调用 clear()函数是对其存放的内容进行一个清理，不写也是可以的，然后还有一点不要忘记的是要判断 digits 为空的情况，这个时候直接返回 result 即可

vector<string> letterCombinations(string digits) {    s.clear();    result.clear();    if(digits == "")        //若输入数串为空，则直接返回        return result;    else        DFS(digits,0);      //若不为空，则递归求解后返回        return result;}

复制代码

整体代码展示

class Solution {private:    //全局变量    string s;               //存放每次的结果    vector<string> result;      //存放最后的结果    map<char,string> table={        {'0'," "},{'1'," "},{'2',"abc"},{'3',"def"},        {'4',"ghi"},{'5',"jkl"},{'6',"mno"},        {'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"},    };    void DFS(const string& digits,int index)    //①递归参数    //digits:表示输入的数串       index:表示单个数串长    {        //递归终止条件        if(index == digits.size())        {            result.push_back(s);            return;        }

        char num = digits[index];   //首先获取是数字键上的哪一个数字        string str = table[num];    //接着根据数字寻找对应的源字符串    
        for(int i=0;i<str.size();++i)       //通过不断回溯查询所有可能结果        {            s.push_back(str[i]);            DFS(digits,index+1);            s.pop_back();        }    };public:    vector<string> letterCombinations(string digits) {        s.clear();        result.clear();        if(digits == "")        //若输入数串为空，则直接返回            return result;        else            DFS(digits,0);      //若不为空，则递归求解后返回            return result;    }};

复制代码

解法二：回溯 + 二维数组

接下来讲解的是第二种方法，这种方法和第一种比较类型，有些地方便会省略

分步讲解

对上一种方法理解之后，就要加深对这道题目的理解了，首先你要明白==三个问题==①数字和字母如何映射？②两个字母就两个 for 循环，三个字符我就三个 for 循环，以此类推，然后发现代码根本写不出来，不断地进行内嵌循环只会导致超时③输入 1 * #按键等等异常情况
这里对于字母的映射不是采用 map，而是另外一种，采用二维数组的方式，虽然没有 map 那么方便，但也是一种思路,这里的前面两个空对应的就是 0 和 1，利用二维数组的下标来表示每个数字，也是一种方法，但可能需要一些转换，也就是字符和数字之间的转换

 const string table[10]{     " "," ","abc","def","ghi",     "jkl","mno","pqrs","tuv","wxyz" };

复制代码

上面提到数字和字符之间的转换，便是对应这里的第一句代码，一样是利用传入的 index 去 digits 数串中一一取出==字符数字==，然后为什么要 - '0'呢，这就是对应的字符转化为数字的常规操作，假设为数字 9，其 Ascll 吗为 57，为数字 0 的 Ascll 码值为 48，两个相减刚好为 9，所以遇到数字字符，将其 - '0'就可以完成转换操作
其余的操作还是一样，因为此时 num 是整型，去二维数组中通过下标就可以访问到对应的字符串

 int num = digits[index] - '0';       //转换成对应数字 string str = table[num];        //根据对应的数字获取相应的字母串 for(int i=0;i<str.size();++i){    s.push_back(str[i]);    backtracking(digits,index+1);      //继续递归    s.pop_back(); }

复制代码

整体代码展示

class Solution {    //全局变量    string s;    vector<string> result;    const string table[10]{        " "," ","abc","def","ghi",        "jkl","mno","pqrs","tuv","wxyz"    };private:    void backtracking(const string& digits,int index){        //digit:数串        index:数串所对应的个数        if(index == digits.size()){         //递归出口            result.push_back(s);    //存放结果            return;        }
        int num = digits[index] - '0';       //转换成对应数字        string str = table[num];        //根据对应的数字获取相应的字母串        for(int i=0;i<str.size();++i){            s.push_back(str[i]);            backtracking(digits,index+1);      //继续递归            s.pop_back();        }    };public:    vector<string> letterCombinations(string digits) {        s.clear();        result.clear();        if(digits == ""){            return result;        }else{            backtracking(digits,0);            return result;        }    }};

复制代码

解法三：队列+ 哈希映射

最后这种方法是我觉得比较巧妙的，思路也比较奇特，可能用哈希映射把 key 通过 hash function 映射为唯一的哈希值，会相对费时间，有时候频繁 insert 的时候其底层的符号表也要做相应的扩充，也是费时的，但这也是一种方法，大家可以将其换成 map 或者是二维数组

本方法可能比较低效一些，但一样拿出来做讲解，有兴趣可以了解一下🦏（最后有==动画详解==）

分步讲解

 if(digits==""){     return {}; }    //处理空字符处理 unordered_map<char, string> phoneMap{     {'2', "abc"},     {'3', "def"},     {'4', "ghi"},     {'5', "jkl"},     {'6', "mno"},     {'7', "pqrs"},     {'8', "tuv"},     {'9', "wxyz"} };

复制代码

首先也是一样，需要将对应的数字字符与字符串进行相应的匹对，这里在哈希映射中只显示了 2~9 这 7 个数字，因为将空字符进行了单独的处理，直接进来就判断 digits 是否为空，若是则直接返回{}
:star2: 队列的思路就是将取出第一个数字字符的每一个字母入队，然后将这几个字母一一出队，与第二个数字所对应的每个字母做一一的组合匹配，然后入队，若是三个数字或者更多，也是一样取出第一个数字与后面进行一一匹配然后入队，直到所有结果都匹配完成

 queue <string> q; int length_of_queue=1; //记录数组长度，便于后续pop全部的元素 q.push(""); //开始给一个空string用于往后面加东西  for(int i=0;i<digits.length();i++){//遍历数组     string str = phoneMap[digits[i]];              for(int k=0;k<length_of_queue;k++){         string a = q.front();     //记录当前出队的字母         q.pop();             //记录并pop队列         for(int j=0;j<str.length();j++){             string c=a+str[j];  //在当前出队的字母后添加对应的字符串                 //向队列加入新的数字对应的字符             q.push(c);                     //加入后入queue         }              }     length_of_queue*=str.length();     //别忘了维护queue长度
 }

复制代码

然后便是开始逐个字符的选取然后对应选取最后进行一个所有可能的筛选拼接，这里是利用了 queue 队列的方法，length_of_queue 是为了记录数组的长度，首先是将此队列放置一个空字符，方便后面入队新元素，接着就开始数组的遍历，这里并没有拿 char 字符来接取，而是直接用 digits[i]放入 phoneMap[]中来寻找对应的字符串然后给到 str
接下去的一个循环就是通过对数组长度的判断来出队并加入新的组合字母，可以先看到后面的这句代码，这就是每次通过接收到的字符串所进行的 queue 长度维护和更新，所以每次

length_of_queue*=str.length();

复制代码

在记录下当前出队的字母后，便将其从队头出队，因为队列的特性就是==先进先出==，最后的内层循环便是遍历 str 字符串，也就是我们在上面通过哈希映射取到的对应字符串。一一地与刚刚出队的字母进行一个拼接，拼接完后继续将其从队尾入队即可，一次循环完成之后就会继续遍历下一个 digits 中的数字字符，开始下一次的循环拼接

 vector <string> result;      //最后在用vector容器接收所有组合结果 while(!q.empty()){     result.push_back(q.front());     q.pop(); } return result;

复制代码

最后，就是定义一个 vector 内置字符串类型的容器，将队列中的元素一个个存入 result 也就是结果集中，为什么要这么做，因为主函数接口需要返回的是这个类型

 vector<string>

复制代码

说了这么多，是不是感觉有点抽象，那大家结合动画看会更加形象一点（有些地方可能看不见动画，电脑端可以），来自此文章

[video(video-9av6aCb6-1660391290247)(type-csdn)(url-https://live.csdn.net/v/embed/231473)(image-https://video-community.csdnimg.cn/vod-84deb4/4ad4890c0df8473188346d8d0cd457f7/snapshots/dd91d535b8a14706b89a7f42eab12b16-00003.jpg?auth_key=4813952071-0-0-2bc1bb92c1191e5d6de26d95c71baffc)(title-)]

对照此动画再结合代码的逻辑，把思路再理一遍，就会发现用这个队列的方法确实挺巧妙的

整体代码展示

class Solution {public:    vector<string> letterCombinations(string digits) {        if(digits==""){            return {};        }        unordered_map<char, string> phoneMap{            {'2', "abc"},            {'3', "def"},            {'4', "ghi"},            {'5', "jkl"},            {'6', "mno"},            {'7', "pqrs"},            {'8', "tuv"},            {'9', "wxyz"}        };        queue <string> q;        int length_of_queue=1;        //记录数组长度，便于后续pop全部的元素        q.push("");        //开始给一个空string用于往后面加东西                for(int i=0;i<digits.length();i++){//遍历数组            string str = phoneMap[digits[i]];                            for(int k=0;k<length_of_queue;k++){                string a = q.front();      //记录当前出队的字母                q.pop();                    //记录并pop队列                for(int j=0;j<str.length();j++){                    string c=a+str[j];  //在当前出队的字母后添加对应的字符串                        //向队列加入新的数字对应的字符                    q.push(c);                            //加入后入queue                }                            }            length_of_queue*=str.length();            //别忘了维护queue长度
        }        vector <string> result;      //最后在用vector容器接收所有组合结果        while(!q.empty()){            result.push_back(q.front());            q.pop();        }        return result;
    }};

复制代码

总结与回顾

最近都在做回溯算法相关的题目，中间给出的三题链接也是相关的，因为题目太多，所以就挑一些比较经典又难以理解的题目给大家讲解，本题本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而下面两题则是求同一个集合中的组合！组合问题在回溯算法当中也是比较经典的，大家学了之后一定要去刷一刷🎇 77. 组合 216.组合总和III
最后，感谢您对本文的观看，如有疑问请于评论区或私信指出

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/8536591ae99fa39d14291e096】。文章转载请联系作者。

Fire_Shield

关注

语言观决定世界观 2022.09.02 加入

高校学生，热爱编程，喜欢写作

发布

暂无评论

创作场景

力扣 17 - 电话号码的字母组合【回溯、哈希映射、队列】

题目描述及分析

题目描述

思路分析

解法一：dfs + map

分步讲解

整体代码展示

解法二：回溯 + 二维数组

分步讲解

整体代码展示

解法三：队列+ 哈希映射

分步讲解

整体代码展示

总结与回顾

Fire_Shield

评论