知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 05 - 电话号码的字母组合 > 💬 **Q:这段代码哪里错了?** > > 问题在这一行: > > ```java > backtrack(digits, nums, index+1, new StringBuilder(), res); > // ^^^^^^^^^^^^^^^^^^^ > // 每次递归都 new 了一个新的空 StringBuilder > ``` > > 你传进去的是一个**全新的空 StringBuilder**,而不是当前已经拼好的 `sb`。所以每一层递归都从空字符串开始,之前 `sb.append` 的内容全部丢失了。 > > **修复:把 `new StringBuilder()` 改成 `sb`:** > > ```java > public void backtrack(String digits, String[] nums, int index, StringBuilder sb, List<String> res) { > if (sb.length() == digits.length()) { > res.add(sb.toString()); > return; > } > int curStr = digits.charAt(index) - '0'; > String curLetter = nums[curStr]; > for (int i = 0; i < curLetter.length(); i++) { > sb.append(curLetter.charAt(i)); > backtrack(digits, nums, index + 1, sb, res); // 传 sb,不是 new StringBuilder() > sb.deleteCharAt(sb.length() - 1); // 回溯,撤销刚才 append 的字符 > } > } > ``` > > 这样递归时 `sb` 里已经有前面拼好的字母,回溯时 `deleteCharAt` 才能正确撤销。 ## 题目(LeetCode 17) 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 ``` 输入:"23" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"] 手机键盘映射: 2 → abc 3 → def 4 → ghi 5 → jkl 6 → mno 7 → pqrs 8 → tuv 9 → wxyz ``` ## 大白话理解 手机九宫格打字。按 2 有 3 个选择(a/b/c),按 3 有 3 个选择(d/e/f),把所有组合列出来。 和前面的题不同:这里不是从一个数组里选,而是每一层的选择列表不同(每个数字对应不同的字母)。 ``` 决策树: 输入 "23" 第 1 层(数字 2 → abc): "" / | \ "a" "b" "c" 第 2 层(数字 3 → def): "a" "b" "c" / | \ / | \ / | \ "ad""ae""af""bd""be""bf""cd""ce""cf" ``` 每一层处理一个数字,选择列表是该数字对应的字母。 ## 代码 ```java class Solution { private static final String[] MAPPING = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; private List<String> result = new ArrayList<>(); public List<String> letterCombinations(String digits) { if (digits.isEmpty()) return result; backtrack(digits, 0, new StringBuilder()); return result; } private void backtrack(String digits, int index, StringBuilder path) { // 终止条件:处理完所有数字 if (index == digits.length()) { result.add(path.toString()); return; } // 当前数字对应的字母 String letters = MAPPING[digits.charAt(index) - '0']; for (char c : letters.toCharArray()) { path.append(c); // 做选择 backtrack(digits, index + 1, path); // 处理下一个数字 path.deleteCharAt(path.length() - 1); // 撤销选择 } } } ``` ### 和排列/子集的区别 ``` 排列/子集:每一层的选择列表是同一个数组 电话号码:每一层的选择列表不同(由当前数字决定) 排列:for (int i = 0; i < nums.length; i++) 子集:for (int i = startIndex; i < nums.length; i++) 电话:for (char c : 当前数字对应的字母) 不需要 startIndex,也不需要 used,因为每层选的是不同的东西 ``` ### 为什么用 StringBuilder? 字符串拼接频繁时,StringBuilder 比 String 拼接高效得多。`append` 和 `deleteCharAt` 就是做选择和撤销选择。 ## 画图模拟 ``` digits = "23" backtrack(index=0, path="") 数字 2 → "abc" 选 'a': backtrack(index=1, path="a") 数字 3 → "def" 选 'd': backtrack(index=2, path="ad") → 收集 "ad" 选 'e': backtrack(index=2, path="ae") → 收集 "ae" 选 'f': backtrack(index=2, path="af") → 收集 "af" 选 'b': backtrack(index=1, path="b") 选 'd': → "bd" 选 'e': → "be" 选 'f': → "bf" 选 'c': backtrack(index=1, path="c") 选 'd': → "cd" 选 'e': → "ce" 选 'f': → "cf" 结果:["ad","ae","af","bd","be","bf","cd","ce","cf"] ``` ## 复杂度 - 时间:O(4^n × n),n 是数字个数,最多每个数字 4 个字母(7 和 9) - 空间:O(n),递归深度 ## 一句话总结 每层的选择列表由当前数字决定,index 控制处理到第几个数字,标准回溯模板。 --- 上一篇:[04 - 组合总和](./04-combination-sum.md) | 下一篇:[06 - 分割回文串](./06-palindrome-partition.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入