刷刷刷 Day 25 | 17. 电话号码的字母组合

17. 电话号码的字母组合

LeetCode题目要求

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例

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

解题思路

首先，根据题目与前面的组合题目有类似之处，但不同的是，本题取组合字母来自于不同的集合。

1. 做电话号码中数字与字母字符串的映射关系，可以使用数组或 Map 方式
2. 回溯三部曲
   回溯三部曲：
   回溯函数及参数：void backtracking(String digits, int num) digits:数字组合 num: 遍历digits的索引
   回溯函数终止条件：digits 的长度即是递归的深度，例子中就是 2
   单层搜索的过程： 取第一层一个字母放入字符串结果，接着递归取第二层，然后需要回溯操作

以例子的 digits = "23" 怎么组合的呢?
①先找到 2 对应字母 abc，进行遍历，并取出 a
②然后递归，在 3 对应的字母 def，进行遍历，取出 d
这时经过①②两部取到了 ad 两个字母，且它们符合要求的结果，那么就存入结果集
后面就是继续遍历与递归了。

上代码

class Solution {

    private Map<Character, String> map = new HashMap<>();

    private void init() {
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
    }

    private List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        // digits 长度范围为 0 - 4
        // digits 为 2 - 9 内的数字 对应的字母 组
        // 映射如下
        // 2:abc
        // 3:def
        // 4:ghi
        // 5:jkl
        // 6:mno
        // 7:pqrs
        // 8:tuv
        // 9:wxyz

        if (digits == null || digits.length() == 0) {
            return res;
        }

        init();
        backtracking(digits, 0);
        return res;
    }

    /**
     * digits : 数字 2-9 范围， 长度为 0-4 的字符串
     * num: 遍历 digits 时的索引
     */
    private void backtracking(String digits, int num) {
        // 如 digits="23"
        // 那么 取 2 对应 value=abc，取 3 对应的 value=def

        // 终止条件, 当遍历完 digits 时，存储结果
        if (digits.length() == num) {
            // 收获结果
            res.add(sb.toString());
            return;
        }

        // 根据 索引 取到 digits 中的 字符数字
        char c = digits.charAt(num);
        // 根据字符数字找到 map 中映射的字母字符串
        String letters = map.get(c);
        // 遍历字母字符串，每次取一个
        for (int i = 0; i < letters.length(); i++) {
            // 取出一个字母存储 StringBuilder
            sb.append(letters.charAt(i));
            // 递归，这里处理的是 digtis 中下一个字母字符串了
            backtracking(digits, num+1);
            // 回溯，把最后一个字母移除
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

重难点

回溯过程，从不同集合取值组合，终止条件

附：学习资料链接