思考方式1

1. 指针t循环遍历234, HashMap作为字典dict存储键盘映射关系
2. 对于每个t, 从dict中获取数字对应的字符串st, 如2->”abc”
   2.1 遍历”abc”, 此时发现这只能横向把abc遍历完, 无法保证2a, 3d, 4g的纵向遍历; 需要改成能纵向遍历的方法. 也就是递归.

递归进阶

1. 从思路1中可知, 数字字符串digits的长度决定了递归的深度, 于是递归基的返回条件为 递归深度>=digits的长度.
2. 递归的每一层,都对应一个数字, 用指针t遍历该数字对应的字符串, 如2->”abc”
3. 对于每一个t, 先取出字符后拼接到上层单词的末尾, 此时不能横向遍历了, 需要深入一层, 直到digits被遍历完, 最后一层遍历结束时, 需要将单词恢复成空字符串, 以开始第二个数字的深度遍历.

234 -> abc | def | ghi

                2      a   |    b     |    c
                3 ad ae af | bd be bf | ca ce cf
            4 adg adh adi | aeg aeh aei | afg afh afi ...() | cfg cfh cfi

234的长度决定深度
第0层 2->abc的长度3
第1层 3->def的长度3
第2层 4->ghi的长度3
3 * 3 * 3 决定宽度

代码框架

• 1 digits记录数字串, dict记录键盘, res记录结果集, w = “” 记录一个结果, level=0记录dfs递归深度
• 2 dfs内部, 对于每一个level
  • 2.1 digit = digits.substring(level,level+1), ds = dict.git(digit)记录数字对应的字母串
  • 2.2 指针i遍历字母串ds, 对于每一个ds[i]
    • 2.2.1 w += ds[i], 将当前字母追加到结果字符末尾,如 g + m = gm
    • 2.2.2 dfs(level+1), 进入下一层找下一个数字
    • 2.2.3 w = “”, dfs已经遍历到最后一层才会到这一句, 此时需要将w恢复成空串状态
  • 2.3 递归基(递归的结束条件):
    • 2.3.1 如果level >= digits.length(),
    • 2.3.2 将补充完整的w添加到结果集中res.add(w),
    • 2.3.3 return
• 3 dfs的参数根据第2步需要进行设置
• 4 边界条件: “”.equals(digits) return res

java dfs深搜

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if(digits == null || "".equals(digits)) return res;
        Map<String,String> dict = new HashMap<>(){{
            put("2", "abc");
            put("3", "def");
            put("4", "ghi");
            put("5", "jkl");
            put("6", "mno");
            put("7", "pqrs");
            put("8", "tuv");
            put("9", "wxyz");
        }};
        dfs(digits, 0, dict, "", res); 
        return res;
    }

    public void dfs(String digits, int level, Map<String, String> dict, String w, List<String> res){
        if(level >= digits.length()) { 
            res.add(w);
            return;
        }
        String digit_str = dict.get(digits.substring(level, level+1));
        for(int i =0;i < digit_str.length();i++){
            w += digit_str.substring(i, i+1);
            // System.out.println(digits.substring(level, level+1)+", "+level + ",digit_str="+digit_str+","+digit_str.substring(i, i+1)+",w="+w);
            dfs(digits, level+1, dict, w, res);
            w = w.substring(0, w.length()-1);
        }
    }
}

二刷, dfs参数更简洁, 写题不用画图了. 20200711

class Solution {
    String[] map = new String[]{
        "", "", "abc", "def",
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz" 
    };
    List<String> res = new ArrayList();
    public List<String> letterCombinations(String digits) {
        //参数2: 表示digits的第i个数字
        dfs(digits, 0, "");
        return res;
    }

    public void dfs(String dg, int u, String path){
        if(dg.length() == u){
            res.add(path);
            return;
        }
        for(int i = 0; i < map[dg.charAt(u)-'0'].length(); i++){
            dfs(dg, u+1, path + map[dg.charAt(u)-'0'].charAt(i) + "");
        }
    }
}