【面试经典 150 | 回溯】电话号码的字母组合

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【字符串】【回溯】

题目来源

17. 电话号码的字母组合

解题思路

方法一：回溯

思路

给定一个仅包含数字 2-9 的字符，现在需要返回它能表示的字母组合。每个数字会和几个字符形成映射，因此需要先使用一个哈希表建立映射关系。

建立好哈希表之后，利用「回溯」枚举出所有可能的字母组合。所谓的「回溯」指的是从问题的某一状态出发沿着某一分支前进，当这条分支走到尽头时，回退一步，从另一种可能的状态出发，如此往复，直至走完所有的路径。

对于示例 1 就是从数字字符的第一个字符 ‘2’ 出发，‘2’ 在哈希表中对应三个字符 ，我们选择一个字符作为分支出发，比如字符 ‘a’；继续出发遇到第二个数字字符 ‘3’，‘3’ 在哈希表中也对应三个字符 ，比如我们选择字符 ‘d’ 出发，这时走到路径尽头了；于是回退一步从 ‘3’ 在哈希表中对应的三个字符出选出另一个字符…如此便可以得到 “ad”、“ae”、“af” 三个字符。这时候再回退一步从 ‘2’ 在哈希表中对应的三个字符出选出另一个字符，如此就能依次得到字符 “bd”, “be”, “bf”, “cd”, “ce”, “cf”。

代码

class Solution {
private:
    unordered_map<char, string> num2Alpha = {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}
    };    
    vector<string> ret;
    string str;
    
    void dfs(string digits, int idex){
        if(idex == digits.size()){
            ret.push_back(str);
            return;
        }

        string alpha = num2Alpha[digits[idex]];
        for(auto &c : alpha){
            str.push_back(c);
            dfs(digits, idex+1);
            str.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()){
            return ret;
        }
        
        dfs(digits, 0);
        return ret;
    }
};

复杂度分析

时间复杂度：$O(3^m\times 4^m)$，其中 $m$ 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），$n$ 是输入中对应 4 个字母的数字个数（包括数字 7、9）。当输入包含 $m$ 个对应 3 个字母的数字和 $n$ 个对应 4 个字母的数字时，不同的字母组合一共有 $3^m\times 4^n$ 种，需要遍历每一种字母组合。

空间复杂度：$O(m+n)$。空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 $m+n$。

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。