0017. Letter Combinations of a Phone Number¶
题目信息¶
- 题号:
电话号码的字母组合
- 难度:
Medium
- 主题:
字符串、回溯、笛卡尔积
- 原题:
- 重点:
逐位扩展前缀、复用回溯路径、由分支数乘积确定输出规模
题目重述¶
给定一个只包含数字 2 到 9 的字符串 digits,按照电话键盘映射返回所有可能的字母组合:
2 -> abc、3 -> def、4 -> ghi、5 -> jkl、6 -> mno、7 -> pqrs、
8 -> tuv、9 -> wxyz。
每个数字必须选择恰好一个对应字母,组合中的字符顺序必须与数字顺序一致。若 digits 为空,返回空列表。
结果顺序不限。
自建示例¶
两个三字母按键:
digits = "23",返回["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"];三字母与四字母按键:
digits = "27",共有3 * 4 = 12个组合;单个数字:
digits = "8",返回["t", "u", "v"];重复数字:
digits = "22",两个位置独立选择,共有3 * 3 = 9个组合;空输入:
digits = "",返回[]。
C++ 实现¶
#include <array>
#include <string>
#include <vector>
class Solution {
private:
const std::array<std::string, 10> letters{
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
std::vector<std::string> iterativeProduct(const std::string& digits) {
if (digits.empty()) {
return {};
}
std::vector<std::string> result{""};
for (char digit : digits) {
const std::string& choices = letters[digit - '0'];
std::vector<std::string> next;
next.reserve(result.size() * choices.size());
for (const std::string& prefix : result) {
for (char letter : choices) {
next.push_back(prefix + letter);
}
}
result.swap(next);
}
return result;
}
void backtrack(const std::string& digits, int index, std::string& path,
std::vector<std::string>& result) {
if (index == static_cast<int>(digits.size())) {
result.push_back(path);
return;
}
for (char letter : letters[digits[index] - '0']) {
path.push_back(letter);
backtrack(digits, index + 1, path, result);
path.pop_back();
}
}
std::vector<std::string> backtrackingProduct(const std::string& digits) {
if (digits.empty()) {
return {};
}
int combinationCount = 1;
for (char digit : digits) {
combinationCount *= static_cast<int>(letters[digit - '0'].size());
}
std::vector<std::string> result;
result.reserve(combinationCount);
std::string path;
path.reserve(digits.size());
backtrack(digits, 0, path, result);
return result;
}
public:
std::vector<std::string> letterCombinations(std::string digits) {
return backtrackingProduct(digits);
}
};
题解¶
组合结构¶
第 i 个数字只决定答案中第 i 个字符的可选集合。例如 digits = "27" 时:
第 0 位从
abc中选择;第 1 位从
pqrs中选择。
每个完整答案都必须从每个集合中各取一个字符,因此答案就是这些按键字母集合按输入顺序形成的笛卡尔积。
若各位置分别有 b0, b1, ..., bk-1 个选择,答案数量为:
N = b0 * b1 * ... * bk-1。
这意味着算法无法少于 N 次生成工作,因为这些答案本身都必须返回。
逐层扩展¶
iterativeProduct 从唯一的空前缀 "" 开始。处理一个数字时,把当前每个前缀分别追加该按键的所有字母,
得到下一层前缀集合。
处理完前 i 个数字后,result 恰好包含这 i 个位置的全部组合:
初始时处理了零个位置,空前缀是唯一组合;
假设当前已经包含前
i位的全部组合;给每个前缀分别追加第
i位的全部合法字母,就得到前i + 1位的全部组合,且没有重复。
这种方法直接保存每一层的全部中间字符串。结构直观,但 prefix + letter 会为每个新节点构造一个新字符串。
回溯状态¶
回溯只需要两个核心状态:
index:下一个需要选择字母的数字位置;path:前index个位置已经选出的前缀。
当前位置的选择集合由 digits[index] 唯一确定。不同位置可以选择相同字母,因此不需要访问标记,也不存在
“某个字母已经使用过”的限制。
每次选择一个字母后执行三步:
追加字母 -> 递归处理下一位 -> 删除末尾字母。
递归返回时删除刚加入的字符,path 就恢复为进入本层前的父前缀。下一次循环可以复用同一个字符串缓冲区,
不会混入上一分支的选择。
叶节点¶
当 index == digits.size() 时,每个数字都已经贡献一个字符,此时 path 的长度恰好等于输入长度,可以
复制到结果中。
每个合法组合对应唯一的一条逐位选择路径;回溯在每一层遍历当前按键的全部字母,所以所有路径都会到达一次。 不同组合至少在一个位置选择不同,因此不会生成重复答案。
空输入¶
若直接从空前缀开始回溯,空输入会立即到达叶节点并产生 [""]。题目要求的结果是空列表,因此两个入口
都先单独处理 digits.empty(),把“没有数字”与“已经为所有数字完成选择”区分开。
代码演进¶
iterativeProduct 用一个结果数组保存当前整层前缀,再构造下一层数组。它把笛卡尔积的逐层展开直接写成循环。
backtrackingProduct 删除中间层数组,只保留一个可变 path。内部节点只执行追加与撤销,完整字符串只在
叶节点复制。combinationCount 由各按键分支数的乘积得到,用于提前预留结果容量,不参与搜索逻辑。
公开入口采用 backtrackingProduct。它与组合树结构一一对应,并把除最终答案外的工作状态压缩到一条当前路径。
复杂度分析¶
设数字长度为 k,答案数量为 N。每个答案长度为 k,复制到结果需要 O(k),因此两种方法的
总时间复杂度都是 O(Nk),返回结果占 O(Nk) 空间。
迭代方法还保存当前层和下一层的中间字符串。回溯方法除返回结果外只使用长度为 k 的路径和递归栈,工作
空间为 O(k)。最坏情况下每个数字有四个字母,N = 4^k,时间可写为 O(k * 4^k)。