【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;//全局mappublic 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);//回溯删掉字符串最后一个字符}}
}