当前位置：首页 > news >正文

LeetCode 17. 电话号码的字母组合 | 深度解析 + 高效回溯实现

news 2026/6/2 23:00:23

一、题目介绍

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; }