一、题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
17. 电话号码的字母组合 - 图1

点击查看原题
难度级别：中等

二、思路

1）回溯法

将每个数字位对应的字符看作树的多个分支，那么本题的思路就变成了多叉树的dfs，当遍历到叶子节点时，记录下根到叶子节点的路径

三、代码

1）回溯法

  1. class Solution {
  2.     private List<List<Character>> mapping = new ArrayList();    // 用list记录数字对应的字母
  3.     List<String> ans;
  4.     public Solution() {
  5.         mapping.add(new ArrayList(Arrays.asList('a', 'b', 'c')));
  6.         mapping.add(new ArrayList(Arrays.asList('d', 'e', 'f')));
  7.         mapping.add(new ArrayList(Arrays.asList('g', 'h', 'i')));
  8.         mapping.add(new ArrayList(Arrays.asList('j', 'k', 'l')));
  9.         mapping.add(new ArrayList(Arrays.asList('m', 'n', 'o')));
  10.         mapping.add(new ArrayList(Arrays.asList('p', 'q', 'r', 's')));
  11.         mapping.add(new ArrayList(Arrays.asList('t', 'u', 'v')));
  12.         mapping.add(new ArrayList(Arrays.asList('w', 'x', 'y', 'z')));
  13.     }
  14.     public List<String> letterCombinations(String digits) {
  15.         if (digits == null || digits.length() == 0) {
  16.             return new ArrayList();
  17.         }
  18.         ans = new ArrayList();
  19.         StringBuilder temp = new StringBuilder();
  20.         dfs(temp, digits.toCharArray(), 0);
  21.         return ans;
  22.     }
  23.     public void dfs(StringBuilder temp, char[] cs, int loc) {
  24.         if (loc == cs.length) {        // 出口条件
  25.             ans.add(temp.toString());
  26.             return ;
  27.         }
  28.         for (char c : mapping.get(cs[loc] - '2')) {
  29.             temp.append(c);
  30.             dfs(temp, cs, loc + 1);
  31.             temp.deleteCharAt(temp.length() - 1);
  32.         }
  33.     }
  34. }

m是digits中对应3个字母的数字个数，n是digits中对应4个字母的数字个数，时时间复杂度为O(3``m``_*_4``n``)，空间复杂度为O(m+n)