题目地址

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;
    }
}