题目描述

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

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

示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

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

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

思路分析

• 今天的算法每日一题是电话号码的字母组合问题，题意明了，接近现实。题目要求我们枚举出所有组合的情况。

• 我们首先需要根据 digits 找出 digit 对应的 letters, 一般采用 hashMap 的方式存储，提升查找效率。

• 除了1之外，每个 digit 对应 3 个 letter。因此，我们需要遍历 letters, 对于每一个 letter 都有选和不选两种情况，我们分别处理。

• dfs 的终止条件是 当前 digit 的索引位置，等于 digits.length()。具体实现代码如下：

通过代码

class Solution {
    public List letterCombinations(String digits) {
        List ans = new ArrayList<>();
        if (digits.length() == 0) {
            return ans;
        }

        Map phoneMap = new HashMap() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};


        dfs(ans, phoneMap, digits, 0, new StringBuffer());

        return ans;
    }


    public void dfs(List ans, Map phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            ans.add(combination.toString());
            return;
        }

        char digit = digits.charAt(index);
        String letters = phoneMap.get(digit);
        int lettersCount = letters.length();
        for (int i = 0; i < lettersCount; i++) {
            combination.append(letters.charAt(i));
            dfs(ans, phoneMap, digits, index + 1, combination);
            combination.deleteCharAt(index);
        }
    }
}

总结

• 今天这个题目非常好，贴近实际，易于理解。结合了 dfs, hashmap 等知识考核。我们需要多练习几次，掌握知识的综合应用。

• 坚持算法每日一题，加油！