回溯中等1 种解法

#17电话号码的字母组合

按数字到字母的映射逐位选择字符，枚举所有可能的字符串。

#回溯#字符串#哈希映射

解题主线

递归层数就是输入数字的下标，每层只需遍历该数字对应的 3 或 4 个字母。

StringBuilder 共享路径并在返回后删除末尾字符，避免每层都创建新字符串。

解法 1：索引回溯

用 index 指向当前数字，把映射到的每个字母加入路径；当 index 到达末尾时复制路径字符串。

时间复杂度

O(4^n × n)，最多产生 4^n 个长度为 n 的结果

空间复杂度

O(n)，不计输出，包含递归栈和路径

17. 电话号码的字母组合 · 索引回溯

java

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) {
        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);
        }
    }
}

用 index 指向当前数字，把映射到的每个字母加入路径；当 index 到达末尾时复制路径字符串。

边界与易错点

空字符串应返回空结果，而不是包含一个空字符串的列表。
映射数组只覆盖数字 2 到 9；若方法可能接收外部输入，应显式拒绝 0、1 和非数字字符。
结果与路径必须在每次调用时创建，不能保留在实例字段中造成重复调用污染。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

backtrack/Q017_letterCombinations.java