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简单的就可以建立数字与字母之间的关联，代码如下所示：
1 class Solution { 2 public: 3 vector<string> letterCombinations(string digits) { 4 if(!digits.size()) 5 return ret; 6 createDic(dic); 7 dfs(0, digits.size(), digits, ""); 8 return ret; 9 10 } 11 12 void createDic(map<char, vector<char>> & dic) 13 { 14 dic['2'].push_back('a'); 15 dic['2'].push_back('b'); 16 dic['2'].push_back('c'); 17 dic['3'].push_back('d'); 18 dic['3'].push_back('e'); 19 dic['3'].push_back('f'); 20 dic['4'].push_back('g'); 21 dic['4'].push_back('h'); 22 dic['4'].push_back('i'); 23 dic['5'].push_back('j'); 24 dic['5'].push_back('k'); 25 dic['5'].push_back('l'); 26 dic['6'].push_back('m'); 27 dic['6'].push_back('n'); 28 dic['6'].push_back('o'); 29 dic['7'].push_back('p'); 30 dic['7'].push_back('q'); 31 dic['7'].push_back('r'); 32 dic['7'].push_back('s'); 33 dic['8'].push_back('t'); 34 dic['8'].push_back('u'); 35 dic['8'].push_back('v'); 36 dic['9'].push_back('w'); 37 dic['9'].push_back('x'); 38 dic['9'].push_back('y'); 39 dic['9'].push_back('z'); 40 } 41 42 43 void dfs(int dep, int maxDep, string & s, string ans) 44 { 45 if(dep == maxDep){ 46 ret.push_back(ans); 47 return; 48 } 49 50 for(int i = 0; i < dic[s[dep]].size(); ++i) //这里的dep应该得到注意 51 dfs(dep+1, maxDep, s, ans + dic[s[dep]][i]) ; 52 } 53 54 private: 55 map<char, vector<char>> dic; 56 vector<string> ret; 57 };