题目地址

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

示例 1：

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

输入：digits = ""
输出：[]
示例 3：

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

提示：

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

题解

暴力枚举

通过遍历来枚举所有状态。

class Solution {
    private static final Map<Character, String> numberToLetters = new HashMap<>();
    static {
        numberToLetters.put('2', "abc");
        numberToLetters.put('3', "def");

        numberToLetters.put('4', "ghi");
        numberToLetters.put('5', "jkl");
        numberToLetters.put('6', "mno");

        numberToLetters.put('7', "pqrs");
        numberToLetters.put('8', "tuv");
        numberToLetters.put('9', "wxyz");
    }

    public List<String> letterCombinations(String digits) {
        List<String> results = new ArrayList<>();
        if (digits.length() == 0) {
            return results;
        }
        
        // 从 "" 作为前缀开始遍历
        results.add("");
        for (int i = 0; i < digits.length(); ++ i) {
            char number = digits.charAt(i);
            String letters = numberToLetters.get(number);
            results = addLetterToPrefix(results, letters);
        }

        return results;
    }

    public List<String> addLetterToPrefix(List<String> prefixs, String letters) {
        List<String> results = new ArrayList<>();
        for (int i = 0; i < prefixs.size(); ++ i) {
            String prefix = prefixs.get(i);
            for (int j = 0; j < letters.length(); ++ j) {
                String result = prefix + letters.charAt(j);
                results.add(result);
            }
        }
        return results;
    }
}

复杂度分析

• 时间复杂度：O(3^m * 4^n)，其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9）。
• 空间复杂度：因为每一个状态都需要一个 String 来保存，因此空间复杂度也是 O(3^m * 4^n)。