难度：
中等
目录
一、问题描述
这里直接采用的是LeetCode上面的问题描述。
给定一个仅包含数字
2-9
的字符串，返回所有它能表示的字母组合。答案可以按
任意顺序
返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
下面给出示例：
提示：
-
0 <= digits.length <= 4
-
digits[i]
是范围
['2', '9']
的一个数字。
二、解题思想
这里我们先要使用 哈希表 将 手机得按键与对应的 字符串 保存起来。
unordered_map<char,string> hashTable{
{'2',"abc"},
{'3',"def"},
{'4',"ghi"},
{'5',"jkl"},
{'6',"mno"},
{'7',"pqrs"},
{'8',"tuv"},
{'9',"wxyz"}
};
这里
传入的字符串的大小 == 每一个解的字符串的长度
。
首先想到的是暴力破解，但是需要循环的层数太多了。转换以下思想，将该结构抽象成树形结构，再使用
DFS
(深度优先搜索) 或者
BFS
(广度优先搜索) 来从头节点遍历到叶子节点，其路径经过的每一个节点组合起来就是解。
举一个例子：例如传入的
digits = “234”
可以抽象成下图：
遍历过程如下：
- 每遍历一个节点保存其节点值至字符串中，直至叶子节点，将此解保存。
- 删除最后一个字符，再回溯至上一层，遍历下一个解。直至到叶子节点才保存解。
具体递归回溯说的也说不清，直接看图（
左边箭头进入递归，右边箭头回溯
）。
下面给出了代码，对应这图会好理解一些。
下面给出步骤图片示意：
三、解题
1、判断极端情况
这里的极端情况就是，传入的
digits.size() == 0
的情况，这时候进行递归会报错，此时直接返回
{ }
即可。
2、代码实现
class Solution {
public:
unordered_map<char,string> hashTable{
{'2',"abc"},
{'3',"def"},
{'4',"ghi"},
{'5',"jkl"},
{'6',"mno"},
{'7',"pqrs"},
{'8',"tuv"},
{'9',"wxyz"}
};
//采用深度优先搜索来遍历所有的可能
void DFS(vector<string>& ans,string an,const string& digits,int index){
//如果到达最大长度，那么就将an 保存下来
if(index == digits.size()){
ans.push_back(an);
}
else{
//每次都找到下一层 对应得 按键 和 字符串
char digit = digits[index];
//将每层对应得字符串 复制到 letters
const string letters = hashTable.at(digit);
//逐个存储每层的 字符
for(auto item : letters){
an.push_back(item);
DFS(ans, an, digits, index+1);
//pop_back() 已经存储至 ans 的字符串 ，回溯至上一层
an.pop_back();
}
}
}
vector<string> letterCombinations(string digits) {
vector<string> ans;
//特殊情况 如果digits 为空则返回 空
if(digits.empty()){
return ans;
}
string an;
DFS(ans, an, digits, 0);
return ans;
}
};
四、总结
对于 递归+回溯 的思想其实对我来说还是比较困难的，我应该明白的也是比较模糊，所以不能描述的很清楚。
多加联系鸭~~
最后还是，如果对你有帮助的话，请star ♥ 一下，收藏一下，蟹蟹啦！👇👇