LeetCode 17 电话号码的字母组合

Posted on Edited on In

LeetCode 17 电话号码的字母组合

题目:
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]
 

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解:
经典回溯算法求全组合
根据提示我们可以得到以下数字-字符数组的映射表: "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"


    

        23456789
    

    

        [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]
    




思路
1.拆分digits= "23" 得数字[2,3]
2.匹配字符数组 charList = [[a,b,c],[d,e,f]] 深度 depth = 2 
3.根据字符数组深度 depth 定义一个同样深度的栈 stack 存储组合的字符
4.对charList从深度0开始递归，递归方式:
    a.判断当前深度是否最深，最深则存储结果返回，否则继续
    b.遍历当前深度所有字符 
    c.每次遍历入栈当前字符
    d.进入下一深度递归
    e.出栈当前字符

图解:
例: digits = "23"
匹配可得字符数组为[[a,b,c],[d,e,f]]

定义字符数组 charList = [[a,b,c],[d,e,f]] 
定义栈深度 depth = 2
定义栈 stack 
定义结果集 list


递归第一层 
取字符 a 入栈
进入第二层递归
Stack
abca
def 

递归第二层 
取字符 d 入栈
此时到达底层，存储结果 "ad"
list = ["ad"]
Stack
abca
defd 

字符 d 出栈
字符 e 入栈
此时到达底层，存储结果 "ae"
list = ["ad","ae"]
Stack
abca
defe 

字符 e 出栈
字符 f 入栈
此时到达底层，存储结果 "af"
list = ["ad","ae","af"]
Stack
abca
deff 

字符 f 出栈
第二层遍历结束，回退回第一层遍历
字符 a 出栈
字符 b 入栈
进入第二层递归
Stack
abcb
def 

递归第二层 
取字符 d 入栈
此时到达底层，存储结果 "bd"
list = ["ad","ae","af","bd"]
Stack
abcb
defd 

字符 d 出栈
字符 e 入栈
此时到达底层，存储结果 "be"
list = ["ad","ae","af","bd","be"]
Stack
abcb
defe 

字符 e 出栈
字符 f 入栈
此时到达底层，存储结果 "bf"
list = ["ad","ae","af","bd","be","bf"]
Stack
abcb
deff 

字符 f 出栈
第二层遍历结束，回退回第一层遍历
字符 b 出栈
字符 c 入栈
进入第二层递归
Stack
abcc
def 

递归第二层 
取字符 d 入栈
此时到达底层，存储结果 "cd"
list = ["ad","ae","af","bd","be","bf","cd"]
Stack
abcc
defd 

字符 d 出栈
字符 e 入栈
此时到达底层，存储结果 "ce"
list = ["ad","ae","af","bd","be","bf","cd","ce"]
Stack
abcc
defe 

字符 e 出栈
字符 f 入栈
此时到达底层，存储结果 "cf"
list = ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Stack
abcc
deff 

字符 f 出栈
第二层遍历结束，回退回第一层遍历
字符 c 出栈
第一层遍历结束
返回结果 list = ["ad","ae","af","bd","be","bf","cd","ce","cf"]

代码：
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
public List<String> letterCombinations(String digits) {
    return process(digits);
}

private List<String> process(String digits) {
    List<String> list = new ArrayList<>();
    if (digits.isEmpty()) return list;
    String[] allChars = new String[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    char [] nums = digits.toCharArray();
    dfs(allChars, nums, 0, new StringBuilder(), list);
    return list;
}

private void dfs(String[] allChars, char[] nums, int depth, StringBuilder s, List<String> list) {
    if (depth == nums.length) {
        list.add(s.toString());
        return;
    }
    int index = nums[depth] - 50;
    char[] chars = allChars[index].toCharArray();
    for (int i = 0; i < chars.length; i++) {
        s.append(chars[i]);
        dfs(allChars, nums, depth + 1, s, list);
        s.deleteCharAt(s.length() - 1);
    }
}