用图的遍历 + 回溯 解决字符组合的枚举。

17.题目链接-来源：力扣（LeetCode）（中等）

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

输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

思路：

要求输出的字符串其实就是按照输入的号码建树，根节点是个空串，第一个数字为2，则分出a, b, c三个子节点，第二个数字为3，每个子节点又继续各自分出d, e, f节点，依此类推，然后进行遍历，输出从根节点出发到每个叶节点的结果。由于需要我们自己建树，所以如果用DFS的话就要用回溯算法；而用BFS的话会比较直观一些，但是需要建一个辅助队列。无论哪种做法，时间复杂度都一样，DFS需要递归层数规模的栈空间，BFS需要创建队列容纳相当于所有结果，需要的堆空间比较多。
时间复杂度：O( $3^m$ * $4^n$) 其中m是对应3个字母的数字个数（也就是2,3,4,5,6,8），n是7,9的个数
空间复杂度：BFS：O(m+n) DFS：O( $3^m$ * $4^n$)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<String> letterCombinations(String digits) { // 还可使用BFS，借助队列
        List<String> combs = new LinkedList<>();
        if (digits.length() == 0) {
            return combs;
        }
        
        Map<Character, char[]> map = new HashMap<>(){{
        put('2', "abc".toCharArray());
        put('3', "def".toCharArray());
        put('4', "ghi".toCharArray());
        put('5', "jkl".toCharArray());
        put('6', "mno".toCharArray());
        put('7', "pqrs".toCharArray());
        put('8', "tuv".toCharArray());
        put('9', "wxyz".toCharArray());
    }};
        
        StringBuilder comb = new StringBuilder();
        backTrack(combs, 0, digits, comb, map);
        return combs;
    }
    
    private void backTrack(List<String> combs, int index, String digits, StringBuilder comb, Map<Character, char[]> map) {
        if (index == digits.length()) {
            combs.add(comb.toString());
        } else {
            char[] choices = map.get(digits.charAt(index));
            for (char c : choices) {
                comb.append(c);
                backTrack(combs, index + 1, digits, comb, map);
                comb.deleteCharAt(index);
            }
        }
    }
}