57.电话号码的字母组合

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

来源：灵茶山艾府

原问题：构造长为n的字符串

子问题：构造长为n-1的字符串

写好边界条件和非边界条件+数学归纳法

这是代码的核心，逻辑是逐位处理数字，对每一位数字的所有字母做遍历，递归拼接后续位的字母，直到所有位处理完毕。

为什么不用回溯？

你可能注意到这段代码没有像之前 “撤销操作”，原因是： 

• path 是固定长度的 char[]，每一位的赋值是 “覆盖式” 的（比如处理第 0 位的 'b' 时，会直接覆盖之前的 'a'），无需手动撤销；
• 只有当 i 走到数字串末尾时，才会把完整的 path 转成字符串存入结果，中间的覆盖操作不会影响已生成的结果。

总结

1. 核心思想：用深度优先搜索（DFS） 逐位处理数字，对每一位数字的所有字母做遍历，递归拼接后续位的字母，直到所有数字处理完毕，生成完整的字母组合。
2. 关键细节：
   • MAPPING 数组是数字到字母的核心映射，通过 digits[i]-'0' 把字符数字转成整数索引，快速获取对应字母。  【类似于char c = ch[i] - 'a' 】
   • 用 char[] 存储当前组合，相比字符串拼接更高效，且无需回溯（覆盖式赋值替代撤销操作）。 ——digits.toCharArray()：把字符串转成字符数组，避免递归中反复调用 charAt(i)，提升性能。
   • 边界条件处理：空输入直接返回空列表，避免无效递归。

class Solution {
    // 核心映射表：索引对应数字（0-9），值对应数字上的字母
    // 0和1无字母，所以用空字符串填充
    private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        int n = digits.length();
        // 边界条件：空字符串直接返回空列表
        if(n==0) return List.of();

        // 存储最终所有字母组合的结果集
        List<String> ans = new ArrayList<>();
        // 用char数组存储当前构建的组合（比StringBuilder更轻量）
        char[] path = new char[n];
        // 启动DFS，从第0个数字开始处理
        dfs(0, ans, path, digits.toCharArray());
        return ans;
    }

    private void dfs(int i, List<String> ans, char[] path, char[] digits){
        // 递归终止条件：所有数字都处理完毕（i等于数字串长度）
        if(i==digits.length){
            // 把当前path数组转成字符串，加入结果集
            ans.add(new String(path));
            return ;
        }

        // 1. 获取当前数字对应的字母串
        // digits[i]是字符（如'2'），减去'0'转成整数2，再取映射表中的字母
        String letters = MAPPING[digits[i]-'0']; 
        // 2. 遍历当前数字的每一个字母
        for(char c : letters.toCharArray()){
            // 把当前字母放到path的第i位（确定第i个位置的字符）
            path[i] = c;
            // 递归处理下一个数字（i+1）
            dfs(i+1, ans, path, digits);
        }
    }
}

下面这段代码类似于两层for循环遍历

        for(char c : letters.toCharArray()){
            // 把当前字母放到path的第i位（确定第i个位置的字符）
            path[i] = c;
            // 递归处理下一个数字（i+1）
            dfs(i+1, ans, path, digits);
        }

【背！！！灵神yyds】