leetcode17：电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

步骤1：定义计算问题性质

题目要求：给定一个数字字符串（仅包含 2-9），按照电话按键的字母映射，返回所有可能的字母组合。

• 输入条件：
  • 一个字符串 digits，仅包含字符 '2'-'9'。
  • 字符串长度范围是 0 <= digits.length <= 4。
• 输出条件：
  • 一个字符串列表，包含所有可能的字母组合。
  • 输出的顺序可以是任意顺序。
• 边界条件：
  • 输入字符串为空，输出应为空列表。
  • 如果输入仅包含一个数字，对应输出是该数字对应的字母组合。

步骤2：分解问题及最佳算法设计

问题分解：

1. 映射构建：定义数字到字母的映射关系。
2. 回溯生成组合：使用回溯法（Backtracking）递归地生成所有组合。

逻辑说明：

• 电话键盘的映射关系是固定的，例如：
  • '2' -> ['a', 'b', 'c']
  • '3' -> ['d', 'e', 'f'] ...
• 回溯法可以有效生成组合：
  • 从输入字符串的第一位开始处理，每处理一位数字时选择其中的一个字母，递归处理剩下的数字。
  • 当处理完最后一个数字时，生成一个完整组合。

时间复杂度：

• 映射构建的复杂度为 O(1)。
• 假设输入长度为 nn 且每个数字对应最多 4 个字母，则组合总数为 4n4^n，回溯遍历所有组合的时间复杂度为 O(4n)O(4^n)。

空间复杂度：

• 主调用栈深度为输入字符串长度 nn，因此空间复杂度为 O(n)O(n)。

步骤3：C++实现代码

// 回溯辅助函数
void backtrack(const string& digits, int index, string& current, vector<string>& result, const vector<string>& mapping) {
    if (index == digits.size()) {
        result.push_back(current); // 当达到末尾，添加当前组合
        return;
    }
    // 获取当前数字对应的字母
    string letters = mapping[digits[index] - '0'];
    for (char letter : letters) {
        current.push_back(letter);      // 选择
        backtrack(digits, index + 1, current, result, mapping); // 递归
        current.pop_back();             // 撤销选择
    }
}

vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {}; // 特殊情况：空输入
    vector<string> mapping = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    }; // 数字到字母的映射
    vector<string> result;
    string current;
    backtrack(digits, 0, current, result, mapping);
    return result;
}

中文注释说明：

1. backtrack 函数是核心逻辑，通过递归逐步构建组合并存储结果。
2. 使用 current 变量存储当前路径，回溯时动态更新。
3. 数字到字母映射存储在 mapping 中，通过 digits[index] - '0' 获取对应字母列表。

步骤4：问题启发

• 递归与回溯的威力：回溯法提供了高效的解决方案，适合于生成排列组合的问题。
• 映射的巧妙设计：通过映射表减少条件判断的复杂性，使得逻辑更加直观。

步骤5：实际生活中的应用

该算法与自动生成所有可能的排列组合有关，可以用于以下场景：

• 短信生成：输入一组数字自动生成候选短信内容。
• 自动化测试：生成测试数据，用于覆盖所有可能的输入组合。

具体应用示例：

• 营销短信生成：
  • 假设公司提供不同产品优惠，通过字母组合生成多种短信内容。例如输入数字 '23'，表示促销两个产品（对应 "abc" 和 "def"）。每种组合代表一种短信模板，算法可以快速生成候选短信内容以供人工筛选。