Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
给出相应的按键,然后要求给出所有可能的字母组合,典型的dfs问题,但是这里的重点在于字典的店里,以及怎么来进行组合,代码如下,原理比较简单,这里就不再赘述了。PS:这题一开始其实没有想明白怎么建立字典,但是实际上通过一个map简单的就可以建立数字与字母之间的关联,代码如下所示:
class Solution {
public:
vector<string> letterCombinations(string digits) {
if(!digits.size())
return ret;
createDic(dic);
dfs(, digits.size(), digits, "");
return ret; } void createDic(map<char, vector<char>> & dic)
{
dic[''].push_back('a');
dic[''].push_back('b');
dic[''].push_back('c');
dic[''].push_back('d');
dic[''].push_back('e');
dic[''].push_back('f');
dic[''].push_back('g');
dic[''].push_back('h');
dic[''].push_back('i');
dic[''].push_back('j');
dic[''].push_back('k');
dic[''].push_back('l');
dic[''].push_back('m');
dic[''].push_back('n');
dic[''].push_back('o');
dic[''].push_back('p');
dic[''].push_back('q');
dic[''].push_back('r');
dic[''].push_back('s');
dic[''].push_back('t');
dic[''].push_back('u');
dic[''].push_back('v');
dic[''].push_back('w');
dic[''].push_back('x');
dic[''].push_back('y');
dic[''].push_back('z');
} void dfs(int dep, int maxDep, string & s, string ans)
{
if(dep == maxDep){
ret.push_back(ans);
return;
} for(int i = ; i < dic[s[dep]].size(); ++i) //这里的dep应该得到注意
dfs(dep+, maxDep, s, ans + dic[s[dep]][i]) ;
} private:
map<char, vector<char>> dic;
vector<string> ret;
};