当前位置：首页 > article >正文

【LeetCode 热题100】17：电话号码的字母组合（详细解析）（Go语言版）

article 2025/9/16 10:08:26

☎️ 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 []stringvar 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 循环尝试每一种选择
常见考点	字符组合、搜索树、剪枝优化（可选）