【字符串】17. 电话号码的字母组合

 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 };