一，知识点
1. 哈希表，字符串，回溯
二， 题目(中等）
给定一个仅包含数字 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 <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
三，思路
如何将数字和字符串对应？可以采用哈希表或数组
一个字符串中字符互不相同，求最后可能的组成字符串的情况？排列组合
类似二叉树的深度优先遍历
画图理解
注意空字符串
四，AC代码
class Solution { char* num[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; public: void mergeCombin(string digits,int di,vector<string>& res,string ch) { if(di==digits.size()) { res.push_back(ch); return; } int n=digits[di]-'0'; string str=num[n]; for(int i=0;i<str.size();++i) { mergeCombin(digits,di+1,res,ch+str[i]); } } vector<string> letterCombinations(string digits) { vector<string> res; if(digits.empty()) return res; string ch; mergeCombin(digits,0,res,ch); return res; } };
