17. 电话号码的字母组合

思路

典型的树形问题，对于输入的数字字符串 23

2代表3种可能，基于a b c考虑下面的情况

可以看到解决这个问题的思路隐藏在一棵树中，因此成为树形问题
因此也可以使用递归结构来解决问题

依次类推

code

class Solution {
    //定义每个数字对应的字母
    private final String[] letterMap = {
          "abc",
          "def",
          "ghi",
          "jkl",
          "mno",
          "pqrs",
          "tuv",
          "wxyz"   //9
      };
      private List<String> res = new ArrayList<>();
      //每次对digits[index]的元素拼接上之前的元素
      //s中保存的是此时从digits[0....index-1]翻译得到的字符串
      //寻找和digits[index]匹配的数字，获得digits[0....index]翻译得到的解
      private void findCombinatin(String digits,int index,String s){
          //如果遍历到头 则得到了一个解
          if(index==digits.length()){
            res.add(s);    
              return;
          }
          //获取对应的数字
        char c = digits.charAt(index);
          //得到对应的字母
          String letters = letterMap[c-'2'];
          //递归拼接上每一个字母 递归对下一个元素 此时拼接上之前的元素
           for(char ch:letters.toCharArray())
            findCombination(digits,index + 1,s + ch);
      }
    public List<String> letterCombinations(String digits) {
          //空字符
          if(digits.equals(""))
              return res;
          //初始index为0 s=""
          findCombinatin(digits,0,"");
          return res;
    }
}