3.电话号码

• 2.12
  • 先找出数字，正在根据数字找字典，在字典内回溯

class Solution {
    String[] dicts = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits==null||digits.length()==0) return res;
        backtrack(digits,new StringBuffer(),0);
        return res;
    }
    public void backtrack(String digits,StringBuffer sb,int index){
        if(index==digits.length()){
            res.add(sb.toString());
            return;
        }
        char digit = digits.charAt(index);
        String letters = dicts[digit-'0'];
        for(int i=0;i<letters.length();i++){
            sb.append(letters.charAt(i));
            backtrack(digits,sb,index+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

• 2.3
  • 难点，思路是用全局 index 参数来控制深度，在具体的字符串内负责广度回溯
  • 难点 1，写一个字符串数组字典
  • 难点 2，想到用 stringbuffer 做 path 存储 char 的组合，以及了解删除与添加字符相关
  • 难点 3，取出字典内的字符串后，在这个桶里面进行回溯

class Solution {
        String[] dict = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        StringBuffer sb = new StringBuffer();
        List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
 
        if(digits==null||digits.length()==0){
            return res;
        }
        backtrack(digits,0);
        return res;
    }
    public void backtrack(String digits,int index){
        if(index==digits.length()){
            res.add(sb.toString());
            return;
        }
        int digit = digits.charAt(index)-'0';
        String letters = dict[digit];
        for(int i=0;i<letters.length();i++){
            sb.append(letters.charAt(i));
            backtrack(digits,index+1);
            sb.deleteCharAt(sb.length()-1);
        }
 
    }
}

• 11.21
  • 与前两个的区别是,他们都在同一个桶内排序,这次是在不同桶内排序(Gemini代码解释还是挺清晰的)
  • 这里的path是StringBuilder,来暂存“路径”
  • 结束条件是满
  • 流程
    • 先按顺序取数字,从map取字符串
    • 遍历字符串的过程中去后面的数字(另一个桶)开始for遍历
    • 记得删除sb.deleteCharAt(sb.length()-1);

class Solution {
    // 1. 建立映射表
    String[] mapping = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder(); // 用来拼凑当前的字符串
    public List<String> letterCombinations(String digits) {
        // 特殊情况处理：如果输入空串，直接返回空列表
        if (digits == null || digits.length() == 0) {
            return res;
        }
        backtrack(digits, 0);
        return res;
    }
    // index: 当前正在处理 digits 中的第几个数字
    public void backtrack(String digits, int index) {
        // 1. 结束条件：如果 index 等于输入长度，说明每位数字都处理完了
        if (index == digits.length()) {
            res.add(sb.toString());
            return;
        }
        // 2. 拿到当前需要处理的数字（比如 '2'）
        // digits.charAt(index) 拿到的是字符 '2'
        // - '0' 是为了把字符 '2' 变成整数 2
        int digit = digits.charAt(index) - '0';
        // 3. 拿到这个数字对应的字母串 (比如 "abc")
        String letters = mapping[digit];
        // 4. 遍历这些字母，做选择
        for (int i = 0; i < letters.length(); i++) {
            char ch = letters.charAt(i);
            // --- 进 (选一个字母) ---
            sb.append(ch);
            // --- 钻 (处理下一个数字，index + 1) ---
            backtrack(digits, index + 1);
            // --- 退 (撤销这个字母，回溯) ---
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}