一、 题目来源与描述题目来源LeetCode 第 17 题 - 电话号码的字母组合 (Medium)题目描述给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意1不对应任何字母。2: abc 3: def 4: ghi 5: jkl 6: mno 7: pqrs 8: tuv 9: wxyz示例输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]二、 核心算法回溯法Backtracking / DFS1. 思路解析这道题本质上是一道排列组合问题。每一个数字对应多个字母我们需要从每个数字对应的字母集合中挑选一个字母拼接成一个完整的字符串。由于字符串的长度不定最多为 4且需要枚举所有可能的组合暴力循环嵌套 for 循环无法动态适应长度。因此我们需要使用回溯算法深度优先搜索 DFS。回溯法的核心思想将问题抽象为一棵决策树N 叉树。树的深度由输入字符串digits的长度决定。节点的分支由当前数字对应的字母数量决定3 或 4 个分支。我们通过递归沿着树的深度遍历当到达叶子节点即处理完所有数字时记录当前路径然后“回溯”到上一层尝试其他分支。2. 回溯三步曲确定递归函数的参数与返回值参数需要包含给定的数字字符串digits以及一个索引index用来标记当前遍历到了哪一个数字。返回值不需要返回值结果直接存入全局变量或类成员变量中。确定终止条件当index digits.size()时说明已经处理完了所有的数字此时将当前拼接好的字符串加入结果集并结束本层递归。确定单层遍历逻辑获取当前index指向的数字对应的字母集letters。使用for循环遍历letters将当前字母加入当前路径path。递归调用下一层index 1。回溯操作将当前字母从path中移除以便尝试下一个字母。三、 代码实现 (C)class Solution { public: // 1. 建立数字到字母的映射表 (使用数组下标直接映射效率极高) const string phone_map[10] { , // 0 , // 1 abc, // 2 def, // 3 ghi, // 4 jkl, // 5 mno, // 6 pqrs, // 7 tuv, // 8 wxyz // 9 }; // 存放最终结果和当前路径的成员变量 vectorstring result; string current_path; // 2. 回溯函数 void backtracking(const string digits, int index) { // 终止条件index 走到头了说明生成了一个完整组合 if (index digits.size()) { result.push_back(current_path); return; } // 获取当前数字对应的字符集 int digit digits[index] - 0; // 字符转整数 string letters phone_map[digit]; // 遍历当前数字对应的所有字母 for (int i 0; i letters.size(); i) { current_path.push_back(letters[i]); // 处理节点加入 backtracking(digits, index 1); // 递归进入下一层 current_path.pop_back(); // 回溯撤销处理 } } // 3. 主函数 vectorstring letterCombinations(string digits) { // 每次调用前清空全局状态 result.clear(); current_path.clear(); // 特殊情况如果输入为空直接返回空数组 if (digits.empty()) { return result; } backtracking(digits, 0); return result; } };四、 复杂度分析时间复杂度O(3M×4N)其中M是输入中对应 3 个字母的数字个数例如 2, 3, 4, 5, 6, 8N是输入中对应 4 个字母的数字个数例如 7, 9MN 是输入数字的总个数。一共有 3M×4N种组合每种组合需要 O(1)的时间拼接字符串在 C 中push_back和pop_back均摊为 O(1)。空间复杂度O(MN)主要取决于递归调用栈的深度最大深度为输入字符串的长度即 MN。此外结果集result的空间不计入算法的辅助空间复杂度。五、 递归与回溯模板总结本题是标准的回溯模板void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; backtracking(路径选择列表); // 递归 回溯撤销处理结果; } }