电话号码的字母组合
📌 定义
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
数字到字母的映射（与电话按键相同）：
- 2: abc
- 3: def
- 4: ghi
- 5: jkl
- 6: mno
- 7: pqrs
- 8: tuv
- 9: wxyz
示例:
输入: digits = "23"
输出: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
输入: digits = ""
输出: []
输入: digits = "2"
输出: ["a","b","c"]
核心思路
使用回溯算法生成笛卡尔积：
- 选择：从当前数字对应的字母中选一个
- 探索：递归处理下一个数字
- 撤销：回溯，尝试其他字母
决策树示例 "23":
""
/ | \
a b c
/ | \ / | \ / | \
d e f d e f d e f
结果: ad,ae,af,bd,be,bf,cd,ce,cf
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(3^n × 4^m) | n个3字母键，m个4字母键 |
| 空间复杂度 | O(n) | 递归栈深度 |
Go 代码
Go 实现
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
phone := map[byte]string{
'2': "abc",
'3': "def",
'4': "ghi",
'5': "jkl",
'6': "mno",
'7': "pqrs",
'8': "tuv",
'9': "wxyz",
}
result := []string{}
path := []byte{}
var backtrack func(index int)
backtrack = func(index int) {
if index == len(digits) {
result = append(result, string(path))
return
}
letters := phone[digits[index]]
for i := 0; i < len(letters); i++ {
path = append(path, letters[i])
backtrack(index + 1)
path = path[:len(path)-1]
}
}
backtrack(0)
return result
}思路展开
回溯过程详解
digits = "23"
backtrack(0, []):
digit='2', letters='abc'
选择'a':
backtrack(1, ['a']):
digit='3', letters='def'
选择'd': backtrack(2, ['a','d']) → 收集"ad"
选择'e': backtrack(2, ['a','e']) → 收集"ae"
选择'f': backtrack(2, ['a','f']) → 收集"af"
选择'b':
backtrack(1, ['b']):
选择'd': 收集"bd"
选择'e': 收集"be"
选择'f': 收集"bf"
选择'c':
backtrack(1, ['c']):
选择'd': 收集"cd"
选择'e': 收集"ce"
选择'f': 收集"cf"
结果: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
经典题目
LeetCode 问题
- 电话号码的字母组合 - LeetCode 17
扩展问题
- 生成所有可能的IP地址
- 生成所有括号组合
⚖️ 优缺点
优点
- ✅ 简单直观：笛卡尔积的直接实现
- ✅ 易于理解：递归逻辑清晰
缺点
- ❌ 指数复杂度：结果数量随输入长度指数增长