企业官网建设流程全解析

一、题目介绍

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 核心思想

这是一道典型的组合型回溯问题，核心逻辑是：

1. 为每个数字建立固定的字母映射表；
2. 递归遍历每个数字对应的字母，逐步构建字母组合（路径）；
3. 当路径长度等于输入数字的长度时，说明已构建完成一个完整组合，将其加入结果集；
4. 回溯过程中复用同一个路径字符串，通过覆盖的方式减少内存开销。

2.2 算法流程

1. 处理边界条件：若输入字符串为空，直接返回空数组；
2. 初始化结果数组和路径字符串（路径长度与输入数字长度一致）；
3. 递归函数（DFS）：
   • 终止条件：当前处理到第n个数字（所有数字处理完毕），将路径加入结果；
   • 遍历当前数字对应的所有字母，将字母填入路径的对应位置，递归处理下一个数字；
4. 最终返回结果数组。

三、完整代码实现

#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 优化点说明

1. 本文的递归实现使用「固定长度路径 + 覆盖式修改」，比传统的「拼接 + 回退」减少了字符串操作的开销；
2. 映射表使用static constexpr，避免重复初始化，提升性能；
3. 递归 lambda 比单独定义递归函数更简洁，代码内聚性更强。

八、总结

本题是回溯算法的经典入门题，核心在于理解「逐步构建组合 + 递归遍历」的思想。本文提供的实现方案有以下特点：

1. 代码简洁高效，利用 C++14 的 lambda 递归简化代码结构；
2. 路径字符串优化，避免频繁拼接和回退操作；
3. 边界条件处理完善，覆盖空输入等特殊情况；
4. 时间 / 空间复杂度最优，符合题目要求。

掌握本题的回溯思想后，可进一步解决类似的组合问题（如组合总和、子集等），是算法学习中不可或缺的基础知识点。