给一个不包含 0 和 1 的数字字符串，每个数字代表一个字母，请返回其所有可能的字母组合。 下图的手机按键图，就表示了每个数字可以代表的字母。

• 以上的答案是按照词典编撰顺序进行输出的，不过，在做本题时，你也可以任意选择你喜欢的输出顺序。

点此做题

样例 1:

输入: "23" 输出: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] 解释:  '2' 可以是 'a', 'b' 或 'c' '3' 可以是 'd', 'e' 或 'f' 

样例 2:

输入: "5" 输出: ["j", "k", "l"] 

算法：DFS

1. 如果输入的数字串为空，返回空列表；
2. 预处理存储 1-9 各个数字可以对应的字母；
3. 对数字串进行深度优先搜索，传入的参数包括：数字串 digits 、当前的位置 index 、当前存入的字符串 current 、保存答案的字符串列表 result 、数字字母映射的字符串数组 phone ；

• 当前位置达到数字串末尾即达到边界，将 current 添加到 result，回溯；
• 对 index 位置的数字通过 phone 找出可以选用的每个字母，分别递归调用 dfs ；
• 递归步进为：index+1，current+选用的字母；

复杂度分析

• 时间复杂度：O(4^n), n 为数字串长度
  • 每个数字都有 3-4 个可对应的字母
• 空间复杂度：O(4^n),n 为数字串长度
  • 对于用来保存答案的列表，最多有 4^n 种组合

public class Solution {     /**      * @param digits: A digital string      * @return: all posible letter combinations      */      public static final HashMap<Integer, String> PHONE = new HashMap<Integer, String>() {         {             put(0, ""); put(1, ""); put(2, "abc"); put(3, "def"); put(4, "ghi");              put(5, "jkl"); put(6, "mno"); put(7, "pqrs"); put(8, "tuv"); put(9, "wxyz");          }     };      public List<String> letterCombinations(String digits) {         List<String> result = new ArrayList<>();         if (digits.length() == 0) {             return result;         }         dfs(0, "", digits, PHONE, result);         return result;     }      private void dfs(int index, String current, String digits, HashMap<Integer, String> PHONE, List<String> result) {         if (index == digits.length()) {             result.add(current);             return;         }          int d = digits.charAt(index) - '0';         for (char c : PHONE.get(d).toCharArray()) {             dfs(index + 1, current + c, digits, PHONE, result);         }     } } 

大佬有話說 (0)