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

       今天我们来解决 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;
}

回溯法解析

1. 映射关系：使用unordered_map建立数字到字母的对应关系，这是问题求解的基础。

2. 回溯函数设计：

   • digits：输入的数字字符串
   • index：当前处理的数字索引
   • current：当前正在构建的字母组合
   • result：存储所有有效组合的结果集

3. 递归过程：

   • 当index等于数字长度时，说明已构建一个完整组合，加入结果集
   • 否则，获取当前数字对应的所有字母，逐个尝试
   • 每个字母都通过递归处理下一个数字，完成后回溯（移除当前字母）

4. 时间复杂度：O (3^N × 4^M)，其中 N 是对应 3 个字母的数字个数，M 是对应 4 个字母的数字个数（7 和 9）

5. 空间复杂度：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;
}

迭代法解析

1. 初始化：从包含一个空字符串的结果列表开始

2. 迭代过程：

   • 对于每个数字，创建临时列表存储新组合
   • 将现有结果中的每个组合与当前数字的每个字母拼接
   • 用新生成的组合替换原结果列表

3. 终止条件：处理完所有数字后，结果列表包含所有可能的组合

4. 时间复杂度：同样是 O (3^N × 4^M)，与回溯法相同

5. 空间复杂度：O (3^N × 4^M)，需要存储所有中间结果

两种方法对比

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

总结

       电话号码的字母组合问题是组合生成类问题的典型代表，通过这道题我们可以深入理解回溯算法的思想。两种解法各有优劣：

• 回溯法通过递归实现，代码简洁直观，空间效率更高，适合处理较长的输入
• 迭代法通过循环实现，避免了递归开销，实现方式巧妙但内存占用较大

       在实际面试中，回溯法是更常被考察的解法，因为它能更好地体现对递归和回溯思想的理解。掌握这两种方法，不仅能解决这道题，还能为解决其他组合、排列类问题打下基础。