308 lines
8.5 KiB
Markdown
308 lines
8.5 KiB
Markdown
---
|
||
tags: ["LeetCode", "回溯", "字符串", "中等"]
|
||
create time: 2026-05-17 11:00
|
||
---
|
||
|
||
# 57-电话号码的字母组合
|
||
|
||
## 题面
|
||
|
||
> **LeetCode 17. Letter Combinations of a Phone Number**
|
||
|
||
给定一个仅包含数字 `2-9` 的字符串，返回所有它能表示的字母组合。答案可以按 **任意顺序** 返回。
|
||
|
||
给出数字到字母的映射如下（与电话按键相同）。注意 `1` 不对应任何字母。
|
||
|
||
```
|
||
2: "abc" 3: "def" 4: "ghi" 5: "jkl"
|
||
6: "mno" 7: "pqrs" 8: "tuv" 9: "wxyz"
|
||
```
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：digits = "23"
|
||
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：digits = "2"
|
||
输出：["a","b","c"]
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- `1 <= digits.length <= 4`
|
||
- `digits[i]` 是范围 `['2', '9']` 的一个数字。
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 思考
|
||
|
||
假设输入是 `"23"`，你会怎么得到所有字母组合？
|
||
|
||
直观做法：先固定 `'2' → "abc"` 中的一个字母，再固定 `'3' → "def"` 中的一个字母，拼成两位字符串。两层循环就能搞定：
|
||
|
||
```go
|
||
for _, a := range "abc" { // 第1层：选2对应的字母
|
||
for _, b := range "def" { // 层：选3对应的字母
|
||
result = append(result, string(a)+string(b))
|
||
}
|
||
}
|
||
```
|
||
|
||
但如果输入是 `"234"` 呢？需要三层嵌套……`"2345"` 就是四层……输入长度不固定，没法手写固定层数的循环。
|
||
|
||
这时就该回溯算法登场了——用递归模拟任意深度的嵌套循环。
|
||
|
||
> [!abstract] 🎯 核心洞察
|
||
|
||
本题的决策树是一棵 **多叉树**，每层的分支数取决于当前数字对应几个字母：
|
||
|
||
| 数字 | 对应字母 | 分支数 |
|
||
|------|---------|--------|
|
||
| 2 | a, b, c | 3 |
|
||
| 3 | d, e, f | 3 |
|
||
| 4 | g, h, i | 3 |
|
||
| 5 | j, k, l | 3 |
|
||
| 6 | m, n, o | 3 |
|
||
| 7 | p, q, r, s | **4** |
|
||
| 8 | t, u, v | 3 |
|
||
| 9 | w, x, y, z | **4** |
|
||
|
||
以 `digits = "23"` 为例，决策过程：
|
||
|
||
```
|
||
先选 2 的字母(a/b/c)，再选 3 的字母(d/e/f) → 拼成结果
|
||
```
|
||
|
||
每个数字是一个决策层，该层有若干候选字母可选，选完一层进入下一层，直到穷尽所有数字。
|
||
|
||
### 回溯框架三要素
|
||
|
||
回溯通用骨架在本题中的具体化：
|
||
|
||
```
|
||
选择某数字对应的一个字母 → 递归处理下一个数字 → 换该数字的下一个字母
|
||
```
|
||
|
||
维护一个 `path` 记录当前拼接的字母序列。与全排列不同，这里不需要 `used[]` ——因为每个数字只访问一次，按索引顺序推进即可。
|
||
|
||
### 回溯决策树（以 `digits = "23"` 为例）
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
root["空 []"] --> A["选 a"]
|
||
root --> B["选 b"]
|
||
root --> C["选 c"]
|
||
|
||
A --> AD["选 d<br/>✅"]
|
||
A --> AE["选 e<br/>✅"]
|
||
A --> AF["选 f<br/>✅"]
|
||
|
||
B --> BD["选 d<br/>✅"]
|
||
B --> BE["选 e<br/>✅"]
|
||
B --> BF["选 f<br/>✅"]
|
||
|
||
C --> CD["选 d<br/>✅"]
|
||
C --> CE["选 e<br/>✅"]
|
||
C --> CF["选 f<br/>✅"]
|
||
|
||
classDef leaf fill:#90EE90,stroke:#228B22,color:#000;
|
||
class AD,AE,AF,BD,BE,BF,CD,CE,CF leaf;
|
||
```
|
||
|
||
> [!note] 🔍 关键观察
|
||
|
||
注意到这是一棵 **"逐层展开"** 的树——不像全排列那样每层都从全部元素中选，而是第 `i` 层只能选 `digits[i]` 对应的那些字母。一旦选完最后一层（深度等于 `digits` 长度），路径就是一条完整的答案。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
> [!abstract] 📝 回溯通用骨架
|
||
|
||
```go
|
||
var digitMap = map[byte]string{
|
||
'2': "abc", '3': "def", '4': "ghi", '5': "jkl",
|
||
'6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
|
||
}
|
||
|
||
var result []string
|
||
|
||
var dfs func(path []byte)
|
||
dfs = func(path []byte) {
|
||
// Base case: 已选满 digits 的长度
|
||
if len(path) == len(digits) {
|
||
result = append(result, string(path))
|
||
return
|
||
}
|
||
|
||
// 找出当前层（第 len(path) 个数字）的候选字母
|
||
ch := digits[len(path)]
|
||
for _, letter := range digitMap[ch] {
|
||
path = append(path, byte(letter)) // 做选择（range string → rune，需转 byte）
|
||
dfs(path) // 递归
|
||
path = path[:len(path)-1] // 撤销选择
|
||
}
|
||
}
|
||
|
||
// 边界：空输入直接返回空数组
|
||
if digits == "" {
|
||
return result
|
||
}
|
||
|
||
dfs(nil)
|
||
return result
|
||
```
|
||
|
||
> [!tip] 🔑 设计细节
|
||
|
||
为什么 Base Case 是 `len(path) == len(digits)` 而不是传一个 `index` 参数？
|
||
|
||
两种方式等价，但利用 `len(path)` 作为隐式索引更简洁——不需要额外传参，也不需要回退时改变 index。代价是每次用 `digits[len(path)]` 做一次切片访问，这在 Go 中是 O(1) 操作，毫无影响。
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式
|
||
|
||
本题属于 **"笛卡尔积"** 类型的回溯——每层独立选择，最终结果是各层候选集的乘积：
|
||
|
||
| 问题类型 | 决策方式 | 代表题目 |
|
||
|---------|---------|---------|
|
||
| **字母组合** | 每层从**当前数字对应的字母集**中选 | LC 17（本题） |
|
||
| **全排列** | 每层从**全部未用元素**中选 | LC 46 |
|
||
| **子集** | 每层**选或不选** | LC 78 |
|
||
|
||
> [!summary] 📋 笛卡尔积 vs 其他回溯
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
CART["笛卡尔积<br/>每层候选集不同<br/>如本题"]
|
||
PERM["全排列<br/>每层从剩余中选<br/>需 used[]"]
|
||
SUB["子集/组合<br/>每层从 start 往后选<br/>start 防回头"]
|
||
|
||
CART -. "同属回溯范式" .-> PERM
|
||
PERM -. "同属回溯范式" .-> SUB
|
||
```
|
||
|
||
> [!danger] ⚠️ 一个易错边界条件
|
||
|
||
**输入为空字符串 `""` 时应该返回 `[]` 而非 `[""]`！**
|
||
|
||
这是面试中最容易翻车的地方。很多初学者看到 `len(path) == 0 == len("")` 就直接把空字符串加入了结果——但实际上空输入不应该产生任何有效组合。
|
||
|
||
```go
|
||
if digits == "" {
|
||
return []string{}
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
> [!success] ✅ 解法：回溯
|
||
|
||
```go
|
||
// letterCombinations 返回 digits 能表示的所有字母组合。
|
||
//
|
||
// 时间复杂度：O(4^k * k) — k 为 digits 长度，最多 4 个字母/位，拼接结果 O(k)
|
||
// 空间复杂度：O(k) — 递归栈深度为 k，k ≤ 4
|
||
func letterCombinations(digits string) []string {
|
||
if digits == "" {
|
||
return []string{}
|
||
}
|
||
|
||
digitMap := [10]string{
|
||
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz",
|
||
}
|
||
|
||
var result []string
|
||
path := make([]byte, 0, len(digits))
|
||
|
||
var dfs func()
|
||
dfs = func() {
|
||
if len(path) == len(digits) {
|
||
result = append(result, string(path))
|
||
return
|
||
}
|
||
|
||
// 取出当前层对应数字的字母集合
|
||
letters := digitMap[digits[len(path)]-'0']
|
||
for i := 0; i < len(letters); i++ {
|
||
path = append(path, letters[i]) // 做选择
|
||
dfs() // 递归进入下一层
|
||
path = path[:len(path)-1] // 撤销选择
|
||
}
|
||
}
|
||
|
||
dfs()
|
||
return result
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 单元测试
|
||
|
||
```go
|
||
import (
|
||
"slices"
|
||
"testing"
|
||
)
|
||
|
||
func TestLetterCombinations(t *testing.T) {
|
||
tests := []struct {
|
||
name string
|
||
input string
|
||
expect []string
|
||
}{
|
||
{name: "示例1", input: "23", expect: []string{"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"}},
|
||
{name: "示例2", input: "2", expect: []string{"a", "b", "c"}},
|
||
{name: "单字符7", input: "7", expect: []string{"p", "q", "r", "s"}},
|
||
{name: "含空串", input: "", expect: []string{}},
|
||
{name: "双7", input: "77", expect: []string{"pp", "pq", "pr", "ps", "qp", "qq", "qr", "qs", "rp", "rq", "rr", "rs", "sp", "sq", "sr", "ss"}},
|
||
}
|
||
|
||
for _, tt := range tests {
|
||
t.Run(tt.name, func(t *testing.T) {
|
||
got := letterCombinations(tt.input)
|
||
slices.Sort(got)
|
||
slices.Sort(tt.expect)
|
||
if !slices.Equal(got, tt.expect) {
|
||
t.Errorf("letterCombinations(%q) = %v; want %v", tt.input, got, tt.expect)
|
||
}
|
||
})
|
||
}
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 总结
|
||
|
||
> [!summary] 📋 本章要点回顾
|
||
|
||
> 电话号码的字母组合是回溯中 **"笛卡尔积型"** 的代表题：
|
||
>
|
||
> 1. **决策特征鲜明**——每层的选择集由当前数字决定，不同于排列的全量选择和子集的选/不选
|
||
> 2. **实现最简回溯**——无需 `used[]`、无需 `start`，一个 `path` 走天下
|
||
> 3. **边界处理关键**——空输入必须特判，否则会得到错误的 `[""]`
|
||
> 4. **复杂度清晰**——4 叉为上限，`k ≤ 4` 的约束下枚举规模极小
|
||
>
|
||
> **口诀**：不进不出只改不回，选了加，回去退，每层候选看数字。
|
||
|
||
---
|
||
|
||
> [!example] 🔀 关联变体题
|
||
|
||
- **[[回溯/55-全排列]]** — 每层从全部未用元素中选，需 `used[]`
|
||
- **[[回溯/56-子集]]** — 二叉决策树，选或不选
|
||
- **LeetCode 980. Unique Paths III** — 带障碍和步数约束的回溯探索
|
||
- **LeetCode 22. Generate Parentheses** — 另一种笛卡尔积变形（状态受限的逐位构造）
|