给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
电话
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
这种求解排列组合的问题，看到组合的字眼第一反应就是回溯法（实际就是DFS、迭代）。或者用队列去做（实际上是BFS），也可以多叉树的问题。代码如下：注意回溯迭代的参数问题：
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
if(!digits.size()) return res;
map<int,string> tel;
tel.insert(pair<int,string>(2,"abc"));
tel.insert(pair<int,string>(3,"def"));
tel.insert(pair<int,string>(4,"ghi"));
tel.insert(pair<int,string>(5,"jkl"));
tel.insert(pair<int,string>(6,"mno"));
tel.insert(pair<int,string>(7,"pqrs"));
tel.insert(pair<int,string>(8,"tuv"));
tel.insert(pair<int,string>(9,"wxyz"));
string tmp = "";
int length = digits.size();
push_it(res,length,tel,digits,0,tmp);
return res;
}
private:
void push_it(vector<string> &res,int length,map<int,string> tel,string digits,int j,string tmp){
if(j==length){
res.push_back(tmp);
tmp = "";
j = 0;
return;
}
for(int i=0;i<tel[digits[j]-'0'].size();i++){
tmp+=tel[digits[j]-'0'].substr(i,1);
push_it(res,length,tel,digits,j+1,tmp);
tmp= tmp.substr(0,tmp.size()-1);
}
return;
}
};
