【LeetCode-中等题】17. 电话号码的字母组合

题目

方法一：递归+回溯

参考讲解：还得用回溯算法！| LeetCode：17.电话号码的字母组合
首先可以画出树图：

• 先将数字对应的字符集合 加入到一个map集合

• 这里需要一个index来控制取数的范围，例如"2 3" 第一次index ==0 代表取 数字2 并且根据2可以从map中取出 2 对应的字符串
• 最终结果集在递归结束的时候收获，也就是要么 index 大于了数字字符串的长度 或者就是最后的要收获的子结果集长度等于数字字符串的长度
  
  代码图示：
  

class Solution {
    // 递归+回溯
    List<String> res = new ArrayList<>();//结果集
    Map<Character,String> map = null;//全局map
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0) return res;
         map = 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");
        }};
        StringBuffer str = new StringBuffer();//子结果集
        int index = 0 ; //用于控制取到哪个数字了 初始默认取0（第一个位置） 2     
        dfsback(digits,index,str);
        return res;
    }
    public void dfsback(String digits,int index,StringBuffer str){
        //  if(str.length() == digits.length()){//递归结束  收获结果      这两个递归终止条件都是可以的
           if(index > digits.length()){//递归结束  收获结果
             res.add(str.toString());
             return;
         }
         String s = map.get(digits.charAt(index));  //取出index位置的数字  并且根据数字获取到对应的字符串
         for(int i = 0 ;i<s.length()  ; i++){
             str.append(s.charAt(i));//加入子结果集
             dfsback(digits,index+1,str);  //index+1  让下一次递归  到下一个数字去取
             str.deleteCharAt(str.length() - 1);//回溯删掉字符串最后一个字符
         }
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35