回溯中等1 种解法
#17电话号码的字母组合
按数字到字母的映射逐位选择字符，枚举所有可能的字符串。
#回溯#字符串#哈希映射
原题
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "2" 输出：["a","b","c"]
提示：
1 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
解题主线
- 递归层数就是输入数字的下标，每层只需遍历该数字对应的 3 或 4 个字母。
- StringBuilder 共享路径并在返回后删除末尾字符，避免每层都创建新字符串。
解法 1：索引回溯
用 index 指向当前数字，把映射到的每个字母加入路径；当 index 到达末尾时复制路径字符串。
-
时间复杂度： O(4^n × n)，最多产生 4^n 个长度为 n 的结果
-
空间复杂度： O(n)，不计输出，包含递归栈和路径
import java.util.ArrayList;
import java.util.List;
final class Solution {
private static final String[] LETTERS = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.isEmpty()) {
return result;
}
for (int i = 0; i < digits.length(); i++) {
char digit = digits.charAt(i);
if (digit < '2' || digit > '9') {
throw new IllegalArgumentException("digits must contain only 2-9");
}
}
backtrack(digits, 0, new StringBuilder(), result);
return result;
}
private void backtrack(String digits, int index, StringBuilder path, List<String> result) {
// index 同时表示递归层数与待处理数字位置，路径长度始终等于 index。
if (index == digits.length()) {
result.add(path.toString());
return;
}
String choices = LETTERS[digits.charAt(index) - '0'];
for (int i = 0; i < choices.length(); i++) {
path.append(choices.charAt(i));
backtrack(digits, index + 1, path, result);
// 撤销本层选择，使同级的下一个字母复用相同前缀。
path.deleteCharAt(path.length() - 1);
}
}
}边界与易错点
- 空字符串应返回空结果，而不是包含一个空字符串的列表。
- 映射数组只覆盖数字 2 到 9；若方法可能接收外部输入，应显式拒绝 0、1 和非数字字符。
- 结果与路径必须在每次调用时创建，不能保留在实例字段中造成重复调用污染。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
backtrack/Q017_letterCombinations.java