电话号码的字母组合

题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

题目链接

Leetcode

题目解答

递归+回溯，先构建数字和字母的对应关系，从字符串首个数字出发，获取数字对应的英文字母串，从字母串首个字母开始，拼接字符，递归处理字符串下一个数字，处理完之后，回溯，删除当前拼接的字符，当字符串索引值与其长度相等的时候，拼接得到的新字符串就是符合要求的一种情况，把它添加到结果列表中，跳出递归，整个递归结束就能得到所有字母组合的结果。

时间复杂度:$O(3^m \times 4^n)$ 空间复杂度:$O(m + n)$

class Solution {
    public String nums = "23456789";
    public List<String> res = new ArrayList<>();
    public Map<Character, String> dict = new HashMap<>();
    public String[] words = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) return res;
        for (int i = 0; i < nums.length(); i++) {
            dict.put(nums.charAt(i), words[i]);
        }
        dfs(digits, 0, new StringBuilder());
        return res;
    }

    public void dfs(String digits, int index, StringBuilder builder) {
        if (index == digits.length()) {
            res.add(builder.toString());
            return;
        }
        String word = dict.get(digits.charAt(index));
        for (int i = 0; i < word.length(); i++) {
            builder.append(word.charAt(i));
            dfs(digits, index + 1, builder);
            builder.deleteCharAt(index);
        }
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了83.34%的用户
内存消耗：37 MB, 在所有 Java 提交中击败了81.79%的用户