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

站长

2022年12月25日 23:37 · 阅读数 11

题目描述及分析

力扣.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来改变每次回溯的起始位置，后续也会出相应讲解:mortar_board: 39.组合总和 78.子集 491.递增子序列
跳过终止条件，先来看后面的过程:point_down:

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回溯具体遍历如图所示:point_down: 力扣17 - 电话号码的字母组合【回溯、哈希映射、队列】

最后就是这个递归的终止条件，因为这个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或者是二维数组

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

分步讲解

 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>

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

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

整体代码展示

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;

    }
};

总结与回顾

最近都在做回溯算法相关的题目，中间给出的三题链接也是相关的，因为题目太多，所以就挑一些比较经典又难以理解的题目给大家讲解，本题本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而下面两题则是求同一个集合中的组合！组合问题在回溯算法当中也是比较经典的，大家学了之后一定要去刷一刷:boom: 77. 组合 216.组合总和III

最后，感谢您对本文的观看，如有疑问请于评论区或私信指出