解法一：深搜

建立字典，然后深度优先搜索

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  5. class Solution {
  6.     private static List<List<Character>> dict = new ArrayList<>();
  8.     static {
  9.         // 2-9
  10.         dict.add(Arrays.asList('a', 'b', 'c'));
  11.         dict.add(Arrays.asList('d', 'e', 'f'));
  12.         dict.add(Arrays.asList('g', 'h', 'i'));
  13.         dict.add(Arrays.asList('j', 'k', 'l'));
  14.         dict.add(Arrays.asList('m', 'n', 'o'));
  15.         dict.add(Arrays.asList('p', 'q', 'r', 's'));
  16.         dict.add(Arrays.asList('t', 'u', 'v'));
  17.         dict.add(Arrays.asList('w', 'x', 'y', 'z'));
  18.     }
  20.     private List<String> ans;
  22.     public List<String> letterCombinations(String digits) {
  23.         ans = new ArrayList<>((int) Math.pow(3, digits.length()));
  24.         if (digits.length() == 0) {
  25.             return ans;
  26.         }
  27.         build(digits.toCharArray(), 0, new char[digits.length()]);
  28.         return ans;
  29.     }
  31.     private void build(final char[] strs, int index, char[] word) {
  32.         if (index == strs.length) {
  33.             ans.add(String.valueOf(word));
  34.             return;
  35.         }
  36.         int digit = strs[index] - 50;
  37.         for (char ch : dict.get(digit)) {
  38.             word[index] = ch;
  39.             build(strs, index + 1, word);
  40.         }
  41.     }
  42. }