--- 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
✅"] A --> AE["选 e
✅"] A --> AF["选 f
✅"] B --> BD["选 d
✅"] B --> BE["选 e
✅"] B --> BF["选 f
✅"] C --> CD["选 d
✅"] C --> CE["选 e
✅"] C --> CF["选 f
✅"] 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["笛卡尔积
每层候选集不同
如本题"] PERM["全排列
每层从剩余中选
需 used[]"] SUB["子集/组合
每层从 start 往后选
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** — 另一种笛卡尔积变形（状态受限的逐位构造）