从零学算法17

17.给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
输入：digits = “”
输出：[]
示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]

首先我们根据每个按键对应的字母先创建一个二维字符数组 tab。分析题目，每个按键对应几个字符，那么当我们组合时，比如示例 1，“2” 对应的字符为 [a,b,c]，即我们在组合时，首位可以为这三种可能，在这三种可能的基础上，我们继续延伸，3 对应为 def，即我们从之前的三种可能可以再分别延伸出三种可能，比如最开始选 a，就能得到 [ad,ae,af]，最开始选 b 就能得到 [bd,be,bf]…。我们可以发现这样从一种可能延伸出其他可能，就像是一棵 n 叉树，只不过根节点的值为空字符。那么我们就 bfs 这棵树得到所有可能。我们用一个 list 从尾部存储结果，取的时候从头取。如果头部的拼接字符串已经等于 digits 的长度了，说明每种可能都拼接完毕。
可以代入例子 1 分析以下代码，res 的变化会经历 [] -> [a,b,c] -> [b,c,ad,ae,af] -> [c,ad,ae,af,bd,be,bf] -> [ad,ae,af,bd,be,bf,cd,ce,cf]

  public List<String> letterCombinations(String digits) {
      LinkedList<String> res = new LinkedList<>();
      //空判断
      if (digits == null || digits.isEmpty())
          return res;
  	  // 按键对应表
      char[][] tab = {{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'},
              {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'},
              {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}};
      // 空字符根节点入队
      res.add("");
      while(res.peek().length() != digits.length()){
          String remove = res.poll();//出队
          // 根据当前拼接字符（或者说当前节点的值）可以判断出我们需要拼接第几个字符
          // 比如最开始为空字符，说明我们要为其拼接第一个字符
          // 它对应的字符为 digits.charAt(remove.length())
          // 由于字符是从 2-9，但是我们的对应表数组下标从 0 开始
          // 即比如字符 2 对应的是 tab[0]
          // 所以这个字符对应的可能选项为：
          // tab[digits.charAt(remove.length()) - '2']
          char[] chars = tab[digits.charAt(remove.length()) - '2'];
          // 拼接每种可能再入队
          for(int i=0;i<chars.length;i++){
              res.add(remove+chars[i]);
          }
      }
      return res;
  }

既然可以 bfs，那么我们难免会想到用 dfs，还是一样的原理，这里的递归终止条件就是得到一种可能，我们就记录并 return，否则还是根据不同的可能性递归。
其实按道理这个逻辑是回溯，所以需要撤销操作，比如我们得到了 ad 后应该复位成 a，再得到 ae->a->af，然后复位成空字符串，继续得到 b->bd->b->be...，否则你可能得到 ad 以后，别的递归部分使用到的 str 就是从 ad 开始拼接得到比如 ade、adef，但是由于递归时每个字符串都是新的对象，不会污染每个可能性分支，也就不用撤销操作了

  LinkedList<String> res = new LinkedList<>();
  char[][] tab = {{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'},
              {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'},
              {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}};
  String digits;
  public List<String> letterCombinations(String digits) {
      // 防空
      if (digits == null || digits.isEmpty())return res;
      this.digits = digits;
      dfs("");
      return res;
  }
  public void dfs(String str){
      if(str.length() == digits.length()){
          res.add(str);
          return;
      }
      char[] chars = tab[digits.charAt(str.length()) - '2'];
      for(int i=0;i<chars.length;i++){
          dfs(str+chars[i]);
      }
  }