【LeetCode】电话号码的字母组合 Java 题解

2021 年 12 月 08 日
本文字数：1133 字
阅读完需：约 4 分钟

题目描述

给定一个仅包含数字 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<String> letterCombinations(String digits) {        List<String> ans = new ArrayList<>();        if (digits.length() == 0) {            return ans;        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{            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<String> ans, Map<Character, String> 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);        }    }}