一、题目介绍
1.1 题目描述
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
数字到字母的映射与电话按键一致（1 不对应任何字母）：
- 2: abc
- 3: def
- 4: ghi
- 5: jkl
- 6: mno
- 7: pqrs
- 8: tuv
- 9: wxyz
1.2 示例
示例 1：输入：digits = "23"输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：输入：digits = "2"输出：["a","b","c"]
示例 3：输入：digits = ""输出：[]
1.3 题目难度
中等
1.4 核心考点
- 回溯算法（深度优先搜索 DFS）的应用
- 字符串的遍历与组合构建
- 递归思想的落地实现
二、解题思路
2.1 核心思想
这是一道典型的组合型回溯问题，核心逻辑是：
- 为每个数字建立固定的字母映射表；
- 递归遍历每个数字对应的字母，逐步构建字母组合（路径）；
- 当路径长度等于输入数字的长度时，说明已构建完成一个完整组合，将其加入结果集；
- 回溯过程中复用同一个路径字符串，通过覆盖的方式减少内存开销。
2.2 算法流程
- 处理边界条件：若输入字符串为空，直接返回空数组；
- 初始化结果数组和路径字符串（路径长度与输入数字长度一致）；
- 递归函数（DFS）：
- 终止条件：当前处理到第
n个数字（所有数字处理完毕），将路径加入结果； - 遍历当前数字对应的所有字母，将字母填入路径的对应位置，递归处理下一个数字；
- 终止条件：当前处理到第
- 最终返回结果数组。
三、完整代码实现
#include <iostream> #include <vector> #include <string> using namespace std; class Solution { // 数字到字母的映射表，索引对应数字0-9 static constexpr string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; public: vector<string> letterCombinations(string digits) { int n = digits.length(); // 边界条件：空字符串直接返回空数组 if (n == 0) { return {}; } vector<string> ans; // 存储最终结果 string path(n, 0); // 路径字符串，长度固定为n，避免频繁拼接 // 递归lambda表达式（C++14及以上支持this auto&&） auto dfs = [&](this auto&& dfs, int i) -> void { // 递归终止：处理完所有数字 if (i == n) { ans.emplace_back(path); // 将当前路径加入结果 return; } // 获取当前数字对应的字母串 const string& letters = MAPPING[digits[i] - '0']; // 遍历当前数字的所有字母 for (char c : letters) { path[i] = c; // 直接覆盖路径的第i位，无需拼接/回退 dfs(i + 1); // 递归处理下一个数字 } }; dfs(0); // 从第0个数字开始递归 return ans; } }; // 测试函数 void test() { Solution s; // 测试案例1 vector<string> res1 = s.letterCombinations("23"); cout << "输入: 23 | 输出: "; for (const string& str : res1) { cout << str << " "; } cout << endl; // 测试案例2 vector<string> res2 = s.letterCombinations("2"); cout << "输入: 2 | 输出: "; for (const string& str : res2) { cout << str << " "; } cout << endl; // 测试案例3 vector<string> res3 = s.letterCombinations(""); cout << "输入: 空 | 输出: " << (res3.empty() ? "空数组" : "非空") << endl; } int main() { test(); return 0; }四、代码深度解析
4.1 映射表定义
static constexpr string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};- 使用
static constexpr定义常量映射表，避免每次调用函数时重复创建，提升性能； - 索引 0 和 1 对应空字符串（因为 0、1 无字母映射），索引 2-9 对应电话按键的字母。
4.2 边界条件处理
if (n == 0) { return {}; }- 输入为空字符串时，直接返回空数组，符合题目要求。
4.3 路径字符串优化
string path(n, 0);- 传统回溯通常使用空字符串逐步拼接，再在递归返回时「回退」（pop_back）；
- 此处直接初始化长度为
n的路径字符串，通过覆盖指定位置的方式构建组合，无需回退操作，减少字符串拼接 / 删除的开销。
4.4 递归 Lambda 表达式
auto dfs = [&](this auto&& dfs, int i) -> void { ... };- C++14 引入的「泛型 lambda」+「this 捕获」，实现递归 lambda（无需额外定义全局 / 类内递归函数）；
this auto&& dfs表示 lambda 自身的引用，用于递归调用；- 捕获列表
[&]表示按引用捕获外部变量（ans、path、digits、MAPPING）。
4.5 递归核心逻辑
if (i == n) { ans.emplace_back(path); return; } for (char c : letters) { path[i] = c; dfs(i + 1); }- 终止条件：
i == n表示所有数字处理完毕，将当前路径加入结果集； - 遍历当前数字的所有字母，将字母填入路径的第
i位，递归处理下一个数字（i+1）； - 由于路径是覆盖式修改，无需手动「回溯」（传统回溯的
pop_back操作），代码更简洁。
五、测试结果
输入: 23 | 输出: ad ae af bd be bf cd ce cf 输入: 2 | 输出: a b c 输入: 空 | 输出: 空数组
完全符合题目预期。
六、算法复杂度分析
6.1 时间复杂度
- 假设输入数字的长度为
n，每个数字对应k个字母（k∈[3,4]）； - 总组合数为
3^n或4^n（取决于数字对应的字母数）； - 时间复杂度：
O(3^n ~ 4^n)，即所有组合的总数。
6.2 空间复杂度
- 递归调用栈的深度为
n（数字长度）； - 路径字符串占用
O(n)空间； - 结果数组占用
O(3^n ~ 4^n)空间（存储所有组合）； - 总空间复杂度：
O(3^n ~ 4^n)。
七、扩展与优化
7.1 非递归（迭代）实现
如果不想使用递归，也可以通过迭代的方式实现：
vector<string> letterCombinations_iter(string digits) { if (digits.empty()) return {}; vector<string> ans = {""}; for (char d : digits) { vector<string> temp; const string& letters = MAPPING[d - '0']; for (const string& s : ans) { for (char c : letters) { temp.push_back(s + c); } } ans.swap(temp); } return ans; }7.2 优化点说明
- 本文的递归实现使用「固定长度路径 + 覆盖式修改」，比传统的「拼接 + 回退」减少了字符串操作的开销；
- 映射表使用
static constexpr，避免重复初始化，提升性能； - 递归 lambda 比单独定义递归函数更简洁，代码内聚性更强。
八、总结
本题是回溯算法的经典入门题，核心在于理解「逐步构建组合 + 递归遍历」的思想。本文提供的实现方案有以下特点：
- 代码简洁高效，利用 C++14 的 lambda 递归简化代码结构；
- 路径字符串优化，避免频繁拼接和回退操作；
- 边界条件处理完善，覆盖空输入等特殊情况；
- 时间 / 空间复杂度最优，符合题目要求。
掌握本题的回溯思想后，可进一步解决类似的组合问题（如组合总和、子集等），是算法学习中不可或缺的基础知识点。
)
