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：分解问题及最佳算法设计

问题分解：

映射构建：定义数字到字母的映射关系。
回溯生成组合：使用回溯法（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;
}

中文注释说明：