17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
class Solution {
public:vector<string> letterCombinations(string digits) {// 用于存储最终结果的字符串数组vector<string> combinations;// 如果输入为空，直接返回空数组（边界情况处理）if (digits.empty()) {return combinations;}// 建立数字到字母的映射哈希表// key: 电话按键字符 (char), value: 对应的字母字符串unordered_map<char, string> phoneMap{{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};// combination: 临时字符串，用于存储当前递归路径上的字母组合string combination;// 调用回溯函数，从第 0 个索引开始处理backtrack(combinations, phoneMap, digits, 0, combination);return combinations;}void backtrack(vector<string>& combinations,const unordered_map<char, string>& phoneMap,const string& digits, size_t index, string& combination) {// --- 递归终止条件 ---// 当 index 等于字符串长度时，说明已经处理完了所有数字if (index == digits.length()) {// 将当前生成的完整组合存入结果集combinations.push_back(combination);return; // 结束当前分支}// 获取当前 index 位置对应的数字字符char digit = digits[index];// 从映射表中获取该数字对应的所有字母字符串const string& letters = phoneMap.at(digit);// --- 遍历当前数字的所有可能字母 ---for (const char& letter : letters) {// 【做选择】：将当前字母加入临时字符串combination.push_back(letter);// 【递归】：处理下一个数字 (index + 1)// 注意这里传入的是 index + 1，表示深入下一层backtrack(combinations, phoneMap, digits, index + 1, combination);// 【回溯/撤销选择】：// 递归返回后，需要把刚才加入的字母删掉，以便尝试当前层的下一个字母// 这就是“回溯”的核心：状态重置combination.pop_back();}}
};class Solution {
public:// temp: 用于临时存储当前正在构建的字母组合（路径）string temp;// res: 用于存储最终所有符合条件的字母组合结果vector<string> res;// board: 电话号码按键映射表，下标 0-9 分别对应按键上的字母// 比如 board[2] = "abc"，代表按键 '2' 对应字母 a, b, cvector<string> board = {"", "", "abc", "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz"};void DFS(int pos, string digits) {// 递归终止条件：当 pos 等于字符串长度时// 说明已经处理完了所有的数字，temp 中存储了一个完整的组合if (pos == digits.size()) {res.push_back(temp); // 将当前完整的组合存入结果集return; // 结束当前递归分支，返回}// 获取当前位置对应的数字字符，并将其转换为整型索引// 例如：digits 是 "23"，pos=0 时，digitVal='2'，num=2int num = digits[pos] - '0';// 遍历当前数字对应的所有字母// 例如：按键 '2' 对应 "abc"，循环就是 a -> b -> cfor (int i = 0; i < board[num].size(); i++) {// --- 处理节点 ---// 将当前字母加入到临时组合 temp 的末尾temp.push_back(board[num][i]);// --- 递归调用 (进入下一层) ---// 处理下一个数字的位置 (pos + 1)DFS(pos + 1, digits);// --- 回溯操作 (撤销处理) ---// 关键步骤：递归返回后，把刚才加入的字母删除// 这样才能在循环的下一次迭代中，尝试同一个按键的下一个字母// 比如试完 'a' 后，删掉 'a'，才能去试 'b'temp.pop_back();}}// 主函数vector<string> letterCombinations(string digits) {// 特判：如果输入为空字符串，直接返回空结果if (digits.size() == 0) {return res;}// 从下标 0 开始进行深度优先搜索DFS(0, digits);// 返回最终生成的所有组合return res;}
};