【训练】【回溯：组合：不同集合】力扣 17. 电话号码的字母组合 ...

题目

   

• 电话号码的字母组合
  

  给定一个仅包含数字 2-9 的字符串，返回全部它能表示的字母组合。答案可以按 恣意次序 返回。
  给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
    示例 1：
  输入：digits = “23”
  输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
    示例 2：
  输入：digits = “”
  输出：[]
    示例 3：
  输入：digits = “2”
  输出：[“a”,“b”,“c”]
  来源：力扣 17. 电话号码的字母组合

---

思路（注意事项）

与之前组合不同的地方在于，这个题是不同集合组合的回溯。

---

纯代码

1. class Solution {
2. private:
3.     string tmp;
4.     vector<string> ans;
5.     string s[10] =
6.     {
7.         "",     // 0
8.         "",     // 1
9.         "abc",  // 2
10.         "def",  // 3
11.         "ghi",  // 4
12.         "jkl",  // 5
13.         "mno",  // 6
14.         "pqrs", // 7
15.         "tuv",  // 8
16.         "wxyz", // 9
17.     };
18.     void backtracking (string digits, int index)
19.     {
20.         if (digits.size() == index)
21.         {
22.             ans.push_back(tmp);
23.             return;
24.         }
26.         string digit = s[digits[index] - '0'];
27.         for (int i = 0; i < digit.size(); i ++)
28.         {
29.             tmp.push_back(digit[i]);
30.             backtracking (digits, index + 1);
31.             tmp.pop_back();
32.         }
33.     }
34. public:
35.     vector<string> letterCombinations(string digits) {
36.         if (digits.size() == 0) return ans;
37.         backtracking (digits, 0);
38.         return ans;
39.     }
40. };

复制代码

题解（加注释）

1. class Solution {
2. private:
3.     string tmp;               // 存储当前正在构建的字母组合，即叶子节点
4.     vector<string> ans;       // 存储所有字母组合的结果，即答案
5.     string s[10] =            // 数字到字母的映射表
6.     {
7.         "",     // 0
8.         "",     // 1
9.         "abc",  // 2
10.         "def",  // 3
11.         "ghi",  // 4
12.         "jkl",  // 5
13.         "mno",  // 6
14.         "pqrs", // 7
15.         "tuv",  // 8
16.         "wxyz", // 9
17.     };
19.     // 回溯函数
20.     void backtracking(string digits, int index) {
21.         // 如果当前组合的长度等于 digits 的长度，说明找到一个有效的组合
22.         if (digits.size() == index) {
23.             ans.push_back(tmp);  // 将当前组合加入结果集
24.             return;
25.         }
27.         // 获取当前数字对应的字母集合
28.         string digit = s[digits[index] - '0'];
30.         // 遍历当前数字对应的所有字母
31.         for (int i = 0; i < digit.size(); i++) {
32.             tmp.push_back(digit[i]);           // 将当前字母加入组合
33.             backtracking(digits, index + 1);   // 递归处理下一个数字
34.             tmp.pop_back();                    // 回溯，移除当前字母
35.         }
36.     }
38. public:
39.     // 主函数：生成所有字母组合
40.     vector<string> letterCombinations(string digits) {
41.         if (digits.size() == 0) return ans;  // 如果输入为空，直接返回空结果
42.         backtracking(digits, 0);             // 从第 0 个数字开始回溯
43.         return ans;                          // 返回所有字母组合
44.     }
45. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。