17. 电话号码的字母组合
一句话套路多叉树按数字逐层展开
题目描述
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:
输入:digits = "23" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
输入:digits = "2" 输出:["a","b","c"]
提示:
1 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
思路
时间
O(4^n · n)(4 来自 7/9 键有 4 个字母)空间
O(n)思路
多叉树,第 i 层就是第 i 个数字的按键表,逐层展开。
易错
输入 "" 必须返回 [](不是 [""])—— 这是本题唯一的坑。
图解
字符串
ad(来自本仓库测试数据,下标从 0 开始)逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0017 {
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> ans;
if (digits.empty()) return ans;
dfs(digits, 0, "", ans);
return ans;
}
private:
static const vector<string>& keys() {
static const vector<string> k{"", "", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"};
return k;
}
static void dfs(const string& digits, int idx, const string& path, vector<string>& ans) {
if (idx == (int)digits.size()) {
ans.push_back(path);
return;
}
for (char c : keys()[digits[idx] - '0']) // 当前数字对应的每个字母都分支一次
dfs(digits, idx + 1, path + c, ans);
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0017::Solution s;
CHECK_EQ(s.letterCombinations("23"),
vector<string>{"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"});
CHECK_EQ(s.letterCombinations(""), vector<string>{}); // 空输入 != {""}
CHECK_EQ(s.letterCombinations("2"), vector<string>{"a", "b", "c"});
CHECK_EQ(s.letterCombinations("79").size(), (size_t)16); // 4×4