☎️ LeetCode 17. 电话号码的字母组合（回溯 + DFS + 详解）
📌 题目描述
给定一个仅包含数字 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"]
💡 解题思路
这道题属于回溯算法的经典题型。类似的题目还有全排列、子集生成等。
✅ 关键点：
- 每一位数字对应多个字母，需要依次尝试。
- 每次从当前位置开始尝试不同的字母，然后递归地构建下一个字符。
- 递归出口是当组合长度等于输入数字的长度。
✍️ 回溯结构大致如下：
func backtrack(path string, index int) {
if len(path) == len(digits) {
res = append(res, path)
return
}
for _, ch := range digitMap[digits[index]] {
backtrack(path + string(ch), index + 1)
}
}
💻 Go 实现代码
func letterCombinations(digits string) []string {
if digits == "" {
return []string{
}
}
digitMap := map[byte]string{
'2': "abc", '3': "def", '4': "ghi",
'5': "jkl", '6': "mno", '7': "pqrs",
'8': "tuv", '9': "wxyz",
}
var res []string
var backtrack func(index int, path string)
backtrack = func(index int, path string) {
if index == len(digits) {
res = append(res, path)
return
}
letters := digitMap[digits[index]]
for i := 0; i < len(letters); i++ {
backtrack(index+1, path+string(letters[i]))
}
}
backtrack(0, "")
return res
}
⏱️ 复杂度分析
| 项目 | 复杂度 |
|---|---|
| 时间复杂度 | \$O(3^n \cdot 4^m)\$，其中 \$n\$ 是出现 3 个字母的数字个数，\$m\$ 是出现 4 个字母的数字个数 |
| 空间复杂度 | \$O(n)\$，递归调用栈的深度 |
🔍 小技巧和注意点
- 初始条件：空字符串
""应该直接返回空结果； - 回溯问题一般都要设计好递归的「终止条件」；
- Go 语言中字符串拼接
path + string(char)会创建新字符串，避免影响回溯路径； - 用 map 存储 digit → 字母 的映射比硬编码效率更高、代码更清晰。
🎯 总结
| 内容 | 要点 |
|---|---|
| 核心思想 | 回溯法构造所有可能组合 |
| 数据结构 | map（映射），递归 |
| 解题模板 | 回溯常规套路：终止条件 + for 循环尝试每一种选择 |
| 常见考点 | 字符组合、搜索树、剪枝优化（可选） |
📚 类似题推荐
💡 小结：
本题是回溯法的经典入门题，重点在于理解「每一步做选择 + 撤销选择」的模式。掌握之后，可以举一反三解决其他排列组合类问题。
如果你喜欢这样的讲解风格，欢迎 点赞 👍 收藏 ⭐ 评论 📝，我会持续带来更多高质量的 LeetCode 题解！
