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

题目

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. 电话号码的字母组合

思路（注意事项）

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

纯代码

class Solution {
private:string tmp;vector<string> ans;string s[10] = {"",     // 0"",     // 1"abc",  // 2"def",  // 3"ghi",  // 4"jkl",  // 5"mno",  // 6"pqrs", // 7"tuv",  // 8"wxyz", // 9};void backtracking (string digits, int index){if (digits.size() == index){ans.push_back(tmp);return;}string digit = s[digits[index] - '0'];for (int i = 0; i < digit.size(); i ++){tmp.push_back(digit[i]);backtracking (digits, index + 1);tmp.pop_back();}}
public:vector<string> letterCombinations(string digits) {if (digits.size() == 0) return ans;backtracking (digits, 0);return ans;}
};

题解（加注释）

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