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

深入解析：每日一算：电话号码的字母组合

news 2025/9/15 20:05:54

深入解析：每日一算：电话号码的字母组合

今天我们来解决 LeetCode 上的经典问题：电话号码的字母组合。这是一道中等难度的题目，非常适合练习回溯算法和递归思想。

问题描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。数字到字母的映射与电话按键相同（1 不对应任何字母）。

示例：

输入："23"，输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
输入：""，输出：[]
输入："2"，输出：["a","b","c"]

解题思路

这道题的核心是要找出数字组合对应的所有可能字母组合，本质上是一个组合问题，可以通过回溯法来解决。

首先，我们需要建立数字到字母的映射关系，然后通过递归的方式生成所有可能的组合。

解法一：回溯法

回溯法是解决这类组合问题的常用方法，它通过深度优先搜索的方式，不断尝试所有可能的选择，当发现选择无法得到有效解时就回溯到上一步，尝试其他选择。

#include
#include
#include
#include
using namespace std;
class Solution {
private:
// 数字到字母的映射表
unordered_map digitMap = {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
// 回溯函数
void backtrack(const string& digits, int index, string& current, vector& result) {
// 递归终止条件：已处理完所有数字
if (index == digits.size()) {
result.push_back(current);
return;
}
// 获取当前数字对应的字母
char digit = digits[index];
string letters = digitMap[digit];
// 尝试当前数字对应的每个字母
for (char letter : letters) {
current.push_back(letter);          // 选择当前字母
backtrack(digits, index + 1, current, result);  // 递归处理下一个数字
current.pop_back();                 // 回溯，撤销选择
}
}
public:
vector letterCombinations(string digits) {
vector result;
// 处理空输入的特殊情况
if (digits.empty()) {
return result;
}
string current;
backtrack(digits, 0, current, result);
return result;
}
};
// 测试函数
void printResult(const vector& result) {
cout << "[";
for (size_t i = 0; i < result.size(); ++i) {
cout << "\"" << result[i] << "\"";
if (i != result.size() - 1) {
cout << ", ";
}
}
cout << "]" << endl;
}
int main() {
Solution solution;
cout << "测试用例 1: digits = \"23\"" << endl;
printResult(solution.letterCombinations("23"));
cout << "测试用例 2: digits = \"\"" << endl;
printResult(solution.letterCombinations(""));
cout << "测试用例 3: digits = \"2\"" << endl;
printResult(solution.letterCombinations("2"));
return 0;
}

回溯法解析

映射关系：使用unordered_map建立数字到字母的对应关系，这是问题求解的基础。
回溯函数设计：
- digits：输入的数字字符串
- index：当前处理的数字索引
- current：当前正在构建的字母组合
- result：存储所有有效组合的结果集
递归过程：
- 当index等于数字长度时，说明已构建一个完整组合，加入结果集
- 否则，获取当前数字对应的所有字母，逐个尝试
- 每个字母都通过递归处理下一个数字，完成后回溯（移除当前字母）
时间复杂度：O (3^N × 4^M)，其中 N 是对应 3 个字母的数字个数，M 是对应 4 个字母的数字个数（7 和 9）
空间复杂度：O (N+M)，主要是递归栈的深度和存储当前组合的空间

解法二：迭代法

除了递归，我们也可以使用迭代的方式，通过循环逐步构建所有可能的组合，这种方法不需要递归调用栈。

#include
#include
#include
#include
using namespace std;
class Solution {
public:
vector letterCombinations(string digits) {
// 处理空输入的特殊情况
if (digits.empty()) {
return {};
}
// 数字到字母的映射表
unordered_map digitMap = {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
// 初始化结果列表，从空字符串开始
vector result = {""};
// 遍历每个数字
for (char digit : digits) {
vector temp;  // 临时存储新生成的组合
string letters = digitMap[digit];
// 遍历现有组合和当前数字的每个字母，生成新组合
for (const string& combo : result) {
for (char letter : letters) {
temp.push_back(combo + letter);
}
}
// 更新结果列表为新生成的组合
result = temp;
}
return result;
}
};
// 测试函数
void printResult(const vector& result) {
cout << "[";
for (size_t i = 0; i < result.size(); ++i) {
cout << "\"" << result[i] << "\"";
if (i != result.size() - 1) {
cout << ", ";
}
}
cout << "]" << endl;
}
int main() {
Solution solution;
cout << "测试用例 1: digits = \"23\"" << endl;
printResult(solution.letterCombinations("23"));
cout << "测试用例 2: digits = \"\"" << endl;
printResult(solution.letterCombinations(""));
cout << "测试用例 3: digits = \"2\"" << endl;
printResult(solution.letterCombinations("2"));
return 0;
}

迭代法解析

初始化：从包含一个空字符串的结果列表开始
迭代过程：
- 对于每个数字，创建临时列表存储新组合
- 将现有结果中的每个组合与当前数字的每个字母拼接
- 用新生成的组合替换原结果列表
终止条件：处理完所有数字后，结果列表包含所有可能的组合
时间复杂度：同样是 O (3^N × 4^M)，与回溯法相同
空间复杂度：O (3^N × 4^M)，需要存储所有中间结果

两种方法对比

方法	实现方式	优点	缺点
回溯法	递归	思路直观，内存占用小	递归调用有栈开销，可能栈溢出
迭代法	循环	无递归开销，更高效	内存占用大，需要存储所有中间结果