17. 电话号码的字母组合
题目描述
输入一个只由数字 2 到 9 组成的字符串 digits。电话按键上每个数字对应几个字母：2→abc，3→def，4→ghi，5→jkl，6→mno，7→pqrs，8→tuv，9→wxyz。数字 1 不对应字母。
依次为每个数字挑一个它对应的字母，按数字顺序拼成一个字符串。返回所有可能拼出的字符串，顺序不限。
示例 1
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
解释：2 可选 a、b、c，3 可选 d、e、f，共 9 种组合。
示例 2
输入：digits = "2" 输出：["a","b","c"]
解释：2 对应 a、b、c 三个字母。
数据范围
1 <= digits.length <= 4digits[i]是'2'到'9'之间的数字。
解题思路：回溯（DFS）
按数字位置逐层回溯。
为什么正确
path 是已处理数字的合法前缀。
复杂度分析
时间 O(4^n·n)，额外空间 O(n)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def letterCombinations(self,d):
if not d:return []
mp=['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'];out=[];p=[]
def f(i):
if i==len(d):out.append(''.join(p));return
for c in mp[int(d[i])]:p.append(c);f(i+1);p.pop()
f(0);return outclass Solution {
private String[] mp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
private List<String> out = new ArrayList<>();
private StringBuilder p = new StringBuilder();
private String digits;
public List<String> letterCombinations(String digits) {
if (digits.isEmpty()) return new ArrayList<>();
this.digits = digits;
f(0);
return out;
}
private void f(int i) {
if (i == digits.length()) {
out.add(p.toString());
return;
}
for (char c : mp[digits.charAt(i) - '0'].toCharArray()) {
p.append(c);
f(i + 1);
p.deleteCharAt(p.length() - 1);
}
}
}class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
vector<string> mp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> out;
string p;
function<void(int)> f = [&](int i) {
if (i == digits.size()) {
out.push_back(p);
return;
}
for (char c : mp[digits[i] - '0']) {
p.push_back(c);
f(i + 1);
p.pop_back();
}
};
f(0);
return out;
}
};func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
mp := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
out := []string{}
p := []byte{}
var f func(i int)
f = func(i int) {
if i == len(digits) {
out = append(out, string(p))
return
}
for _, c := range []byte(mp[digits[i]-'0']) {
p = append(p, c)
f(i + 1)
p = p[:len(p)-1]
}
}
f(0)
return out
}var letterCombinations = function(digits) {
if (!digits) return [];
const mp = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'], out = [], p = [];
const f = (i) => {
if (i === digits.length) {
out.push(p.join(''));
return;
}
for (const c of mp[Number(digits[i])]) {
p.push(c);
f(i + 1);
p.pop();
}
};
f(0);
return out;
};function letterCombinations(digits: string): string[] {
if (!digits) return [];
const mp = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'], out: string[] = [], p: string[] = [];
const f = (i: number): void => {
if (i === digits.length) {
out.push(p.join(''));
return;
}
for (const c of mp[Number(digits[i])]) {
p.push(c);
f(i + 1);
p.pop();
}
};
f(0);
return out;
};其他解法
回溯按深度优先生成，每次只保存一条路径；迭代法按层生成，写法更短但中间结果更多。答案本身已占 O(4^n·n)，两者渐进复杂度相同。
解法 2：逐位扩展（迭代 / BFS） 时间 O(4^n·n)，空间 O(4^n·n)
从只含空串的列表开始。每读入一个数字，就把列表中的每个前缀分别接上该数字对应的每个字母，得到新的一层列表。处理完所有数字后，列表就是全部组合。
没有递归，把搜索树按层展开，类似 BFS，也类似求笛卡尔积。代价是要保存整层的中间结果并反复复制前缀，而回溯只维护一条路径。
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
mp = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
res = ['']
for d in digits:
res = [prefix + c for prefix in res for c in mp[int(d)]]
return resclass Solution {
public List<String> letterCombinations(String digits) {
if (digits.isEmpty()) return new ArrayList<>();
String[] mp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> res = new ArrayList<>();
res.add("");
for (char d : digits.toCharArray()) {
List<String> next = new ArrayList<>();
for (String prefix : res)
for (char c : mp[d - '0'].toCharArray()) next.add(prefix + c);
res = next;
}
return res;
}
}class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
vector<string> mp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> res = {""};
for (char d : digits) {
vector<string> next;
for (const string& prefix : res)
for (char c : mp[d - '0']) next.push_back(prefix + c);
res = move(next);
}
return res;
}
};func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
mp := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
res := []string{""}
for i := 0; i < len(digits); i++ {
next := []string{}
for _, prefix := range res {
for _, c := range mp[digits[i]-'0'] {
next = append(next, prefix+string(c))
}
}
res = next
}
return res
}var letterCombinations = function(digits) {
if (!digits) return [];
const mp = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
let res = [''];
for (const d of digits) {
const next = [];
for (const prefix of res)
for (const c of mp[+d]) next.push(prefix + c);
res = next;
}
return res;
};function letterCombinations(digits: string): string[] {
if (!digits) return [];
const mp = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
let res = [''];
for (const d of digits) {
const next: string[] = [];
for (const prefix of res)
for (const c of mp[+d]) next.push(prefix + c);
res = next;
}
return res;
};