文章目录
- 写在前面
- Tag
- 题目来源
- 解题思路
- 方法一:回溯
- 写在最后
写在前面
本专栏专注于分析与讲解【面试经典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 × 4 m ) O(3^m \times 4^m) O(3m×4m),其中 m m m 是输入中对应 3 个字母的数字个数(包括数字 2、3、4、5、6、8), n n n 是输入中对应 4 个字母的数字个数(包括数字 7、9)。当输入包含 m m m 个对应 3 个字母的数字和 n n n 个对应 4 个字母的数字时,不同的字母组合一共有 3 m × 4 n 3^m \times 4^n 3m×4n 种,需要遍历每一种字母组合。
空间复杂度: O ( m + n ) O(m+n) O(m+n)。空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数,哈希表的大小与输入无关,可以看成常数,递归调用层数最大为 m + n m+n m+n。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。