LeetCode-17. 电话号码的字母组合-Java-medium

题目链接

法一（回溯法）

public class Solution17 {

    private List<String> ans;
    private StringBuilder sb;

    public Solution17() {
        ans = new ArrayList<>();
        sb = new StringBuilder();
    }

    /**
     * 回溯
     *
     * @param digits
     * @param hash
     * @param num
     */
    private void backTracking(String digits, String[] hash, int num) {
        if (num == digits.length()) { // 终止条件
            ans.add(sb.toString());
            return;
        }
        String str = hash[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            backTracking(digits, hash, num + 1); // 递归
            sb.deleteCharAt(sb.length() - 1);  // 回溯，类比求全排列的过程
        }
    }

    /**
     * 回溯法
     * （1）确定回溯函数参数
     * （2）确定终止条件
     * （3）确定单层遍历逻辑
     *
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        String[] hash = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backTracking(digits, hash, 0);
        return ans;
    }
}
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
37
38
39
40
41
42
43
44
45
46
47
48

本地测试

        /**
         * 17. 电话号码的字母组合
         */
        lay.showTitle(17);
        Solution17 sol17 = new Solution17();
        String digits17 = "23";
        List<String> ans17 = sol17.letterCombinations(digits17);
        arrayOpt.showStringList(ans17);
1
2
3
4
5
6
7
8