题目：

 

 

解答：

 1 class Solution {
 2 public:
 3     // 1. 用map记录每个数字按键对应的所有字母
 4     map<char, string> M = {
 5         {\'2\', "abc"}, {\'3\', "def"}, {\'4\', "ghi"}, {\'5\', "jkl"}, {\'6\', "mno"},
 6         {\'7\', "pqrs"}, {\'8\', "tuv"}, {\'9\', "wxyz"}
 7     };
 8 
 9     // 2. 存储最终结果和临时结果的变量
10     vector<string> ans;
11     string current;
12 
13     // 3. DFS函数，index是生成临时结果字串的下标，
14     // 每一个digits[index]数字对应临时结果current[index]的一位字母
15     void DFS(int index, string digits) 
16     {
17         // 出口
18         if(index == digits.size()) 
19         {
20             ans.push_back(current);
21             return;
22         }
23 
24         // 递归调用
25         // 对于当前输入的第index号数字(digits[index])，
26         // 枚举其对应的所有字母(M[digits[index]][i])
27         for(int i = 0; i < M[digits[index]].size(); i++) 
28         {
29             // 临时结果压入一个字母
30             current.push_back(M[digits[index]][i]);     
31             // 以在当前位置压入该字母这一“情况”为前提，构造此“分支”的后续结果
32             DFS(index + 1, digits);         
33             // 状态还原，例如临时结果从 "ab" -> "a"，下一次循环尝试"ac" 
34             current.pop_back();             
35         }
36     }
37 
38     vector<string> letterCombinations(string digits) 
39     {
40         if(digits.size() == 0) 
41         {
42             return ans;
43         }
44         DFS(0, digits);
45         return ans;
46     }
47 };

 

版权声明：本文为ocpc原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/ocpc/p/12825777.html