给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2：
输入：digits = ""
输出：[]示例 3：
输入：digits = "2"
输出：["a","b","c"]提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
解题思路：回溯 + 哈希表
这道题其实就是暴力搜索，要遍历所有的叶子节点拿到所有的结果。其中因为每个位置可选择的字符与其他位置并不冲突，因此不需要标记已经出现的字符，只需要将每个数字对应的字符依次填入字符串中进行递归，然后在回溯时候进行撤销之前的填入操作即可。
只不过为了快速找到当前数字对应的字母组合，我们需要在递归之前我们需要定义一个哈希表 hash，记录 2~9 各自对应的字符。（但实际上在实现的时候，为了方便我们可以直接给出 10 个元素大小的字符串数组即可，其中 0 和 1 都是空串！
接下来的步骤其实就和全排列问题是类似的，要下标 0 处开始遍历所有的结果！只不过要注意的是递归函数出口的细节，因为有可能这道题传入的手机号码是空串，此时题目要求如果是空串的话，返回的结果是什么都没有，所以我们就需要在递归函数出口处判断一下，如果电话号码不是空串再进行添加结果集操作！
class Solution {
private:
string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ret; // 存放结果集
string path; // 存放路径上的字符
public:
vector<string> letterCombinations(string digits) {
dfs(digits, 0);
return ret;
}
void dfs(string& digits, int index)
{
// 递归函数出口
if(index == digits.size())
{
if(digits.size() > 0)
ret.push_back(path);
return;
}
string tmp = hash[digits[index] - '0']; // 先拿到当前数字对应的字符串
for(int i = 0; i < tmp.size(); ++i)
{
// 处理当前节点
path.push_back(tmp[i]);
// 先递归处理该节点下面的其它路径
dfs(digits, index + 1);
// 进行回溯处理
path.pop_back();
}
}
};