回溯法与迭代法详解：如何从手机数字键盘生成字母组合

在这篇文章中，我们将详细介绍如何基于手机数字键盘的映射，给定一个仅包含数字 2-9 的字符串，输出它能够表示的所有字母组合。这是一个经典的回溯算法问题，适合初学者理解和掌握。

问题描述

给定一个数字字符串，比如 digits = "23"，手机数字键盘的映射如下：

2 -> "abc"
3 -> "def"
4 -> "ghi"
5 -> "jkl"
6 -> "mno"
7 -> "pqrs"
8 -> "tuv"
9 -> "wxyz"

我们需要找到所有可能的字母组合。举个例子：

"23" -> ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

17. 电话号码的字母组合 - 力扣（LeetCode）

1. 问题分析

从问题的角度看，这是一个组合问题。手机键盘上的每个数字对应一组字母，我们要找到给定数字的所有字母组合。关键在于如何构建这些组合。我们可以通过回溯法或者迭代法来解决。

1.1 回溯法的思路

回溯算法是递归算法的一种，适合用来枚举所有可能的结果。在这个问题中，回溯的关键点是从第一个数字开始，遍历所有可能的字母组合，逐步构建字符串，直到所有数字都被处理完毕。

具体步骤如下：

1. 选择：我们从 digits 中每个数字开始，找到对应的字母集。
2. 递归：对于字母集中的每个字母，我们递归地去构建字符串，直到遍历完所有的数字。
3. 回退：在递归过程中，构建的字符串达到一定长度后，我们会回退（撤销上一步操作），尝试其他的可能性。

1.2 多种解法

• 回溯法：利用递归去枚举所有可能的组合。复杂度为 $O(3^n)$ 或 $O(4^n)$，取决于输入的数字个数。
• 迭代法：使用队列的方式逐步构造出所有的字母组合。每处理一个数字，都会将当前已有的组合与对应的新字母结合。

接下来我们详细介绍这两种解法。

2. 解法一：回溯法（Backtracking）

2.1 解题思路

回溯算法的基本思路是递归地构建可能的组合，并在递归结束时撤销选择。具体来说，我们会从第一个数字开始，对应的字母集选择一个字母，然后递归处理下一个数字。

回溯的步骤：

1. 如果已经构建的字符串长度等于 digits 的长度，我们就将它加入结果集。
2. 否则，继续处理下一个数字。
3. 每次递归返回时，撤销上一次的选择，尝试下一个字母。

2.2 代码实现

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<string> ans;  // 存储结果
    string combination = "";  // 当前的字母组合

    void backtrack(const string& digits, unordered_map<char, string>& phone, int idx) {
        if (idx == digits.size()) {  // 当达到数字字符串的长度时
            ans.push_back(combination);  // 将组合加入结果集
            return;
        }
        
        char digit = digits[idx];  // 获取当前数字
        const string& letters = phone[digit];  // 获取当前数字对应的字母集
        
        for (char letter : letters) {  // 遍历字母集中的每个字母
            combination += letter;  // 做出选择
            backtrack(digits, phone, idx + 1);  // 递归处理下一个数字
            combination.pop_back();  // 回溯，撤销选择
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};  // 边界情况处理，空输入返回空数组
        
        // 建立数字到字母的映射
        unordered_map<char, string> phone = {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };
        
        // 调用回溯函数
        backtrack(digits, phone, 0);
        
        return ans;  // 返回结果
    }
};

2.3 详细解释

1. 递归终止条件：当索引 idx 达到 digits 的长度时，说明我们已经构造了一个完整的字母组合，将其加入结果集。
2. 递归过程：对于当前数字，找到对应的字母集，遍历字母集中的每一个字母，加入到当前的组合字符串中，然后递归处理下一个数字。
3. 回溯撤销选择：在递归返回后，我们调用 combination.pop_back() 撤销上一次递归中加入的字符，回退到上一个状态，从而尝试下一个字母。

2.4 示例模拟过程

• 输入：digits = "23"
  • 递归过程：
    1. 处理第一个数字 2，对应的字母集是 ['a', 'b', 'c']。
    2. 选中字母 'a'，递归处理下一个数字 3，对应的字母集是 ['d', 'e', 'f']。
    3. 选中字母 'd'，完成组合 'ad'，将其加入结果集。
    4. 回退到字母 'a'，选择下一个字母 'e'，构造组合 'ae'，继续加入结果集。
    5. 继续这种方式，构造出 'af'，然后回退选择字母 'b'。
    6. 重复上述过程直到遍历所有字母，得到组合 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

3. 解法二：迭代法（使用队列）

3.1 解题思路

另一种方法是利用队列。我们可以使用一个队列来逐步生成组合：

1. 从数字字符串的第一个数字开始，把对应的字母放入队列。
2. 对于每一个数字，取出队列中所有的已有组合，然后在每个组合后附加当前数字对应的每一个字母，形成新的组合，再放回队列。
3. 当处理完所有的数字时，队列中保存的就是所有可能的组合。

3.2 代码实现

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};  // 边界情况处理，空输入返回空数组
        
        // 建立数字到字母的映射
        unordered_map<char, string> phone = {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };
        
        queue<string> q;  // 定义一个队列来保存组合
        q.push("");  // 先往队列中放入一个空字符串
        
        // 遍历输入数字字符串中的每个数字
        for (char digit : digits) {
            int n = q.size();  // 记录当前队列的大小
            const string& letters = phone[digit];  // 获取当前数字对应的字母集
            
            for (int i = 0; i < n; i++) {  // 对于当前队列中每个已有组合
                string current = q.front();  // 取出队首元素
                q.pop();  // 移除队首
                
                // 对当前数字的每个字母，将其加到已有组合的后面
                for (char letter : letters) {
                    q.push(current + letter);  // 将新组合放回队列
                }
            }
        }
        
        // 最终队列中的所有元素就是结果
        vector<string> ans;
        while (!q.empty()) {
            ans.push_back(q.front());
            q.pop();
        }
        
        return ans;
    }
};

3.3 示例讲解

• 输入：digits = "23"
  1. 初始化队列：q = [""]。
  2. 处理

第一个数字 2，对应的字母集 ['a', 'b', 'c']。将每个字母加到队列中的每一个已有组合（当前为空字符串 ""），得到队列 q = ["a", "b", "c"]。
3. 处理第二个数字 3，对应的字母集 ['d', 'e', 'f']。将每个字母加到队列中的每一个已有组合，得到 q = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。
4. 最终队列中的元素就是结果。

4. 总结

• 回溯法：通过递归逐步构建可能的组合，并在递归结束后撤销选择，时间复杂度接近 $O(3^n)$ 或 $O(4^n)$，取决于数字对应的字母数量。回溯算法的优点是易于实现，适合处理这种组合问题。

• 迭代法（队列）：通过队列逐步构建组合，时间复杂度也是 $O(3^n)$ 或 $O(4^n)$。虽然有时实现起来可能比递归稍微复杂，但它在一些情况下的性能表现会更好。

对于新手来说，回溯法可能是更直观的解法，因为它的思路清晰，非常适合处理类似的组合问题。