17. 电话号码的字母组合#

class Solution {
    // letterMap：数字到字母的映射表，下标就是数字字符对应的数值
    private String[] letterMap = {
        "",     // 0 不对应字母
        "",     // 1 不对应字母
        "abc",  // 2 对应 abc
        "def",  // 3 对应 def
        "ghi",  // 4 对应 ghi
        "jkl",  // 5 对应 jkl
        "mno",  // 6 对应 mno
        "pqrs", // 7 对应 pqrs
        "tuv",  // 8 对应 tuv
        "wxyz"  // 9 对应 wxyz
    };

    // 主函数：返回输入数字串对应的所有字母组合
    public List<String> letterCombinations(String digits) {
        // res：保存最终组合结果
        List<String> res = new ArrayList<>();
        // 边界处理：空串或 null 时没有任何组合，直接返回空列表
        if(digits == null || digits.length() == 0) 
            return res;

        // 从第 0 个数字开始回溯，path 记录当前正在拼接的组合
        backtrack(res, digits, 0, new StringBuilder());
        // 返回所有组合
        return res;
    }

    // 回溯函数：处理 digits[index] 及其后续数字
    private void backtrack(List<String> res, String digits, int index, StringBuilder path) {
        // 终止条件：当 index 走到 digits 末尾，说明已拼出一个完整组合
        if(index == digits.length()) {
            // 把当前路径转成字符串加入结果
            res.add(path.toString());
            // 当前分支结束，返回上一层
            return;
        }

        // 取出当前数字对应的所有候选字母
        // digits.charAt(index) - '0'：把字符数字转成整型下标
        String letters = letterMap[digits.charAt(index) - '0'];

        // 枚举当前数字可选的每个字母
        for(char letter : letters.toCharArray()) {
            // 做选择：把当前字母追加到路径末尾
            path.append(letter);

            // 递归处理下一个数字
            backtrack(res, digits, index + 1, path);

            // 撤销选择（回溯）：删掉刚追加的字母，尝试下一个候选字母
            path.deleteCharAt(path.length() - 1);
        }
    }
}