题解 | #牛名生成器#

import java.util.*;


public class Solution {
    private static final Map<Character, String> digitToLetters = new HashMap<>();
    static {
        digitToLetters.put('2', "abc");
        digitToLetters.put('3', "def");
        digitToLetters.put('4', "ghi");
        digitToLetters.put('5', "jkl");
        digitToLetters.put('6', "mno");
        digitToLetters.put('7', "pqrs");
        digitToLetters.put('8', "tuv");
        digitToLetters.put('9', "wxyz");
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param digits string字符串
     * @return string字符串一维数组
     */
    public String[] letterCombinations (String digits) {
        // write code here
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result.toArray(new String[0]);
        }
        backtrack(result, new StringBuilder(), digits, 0);
        return result.toArray(new String[0]);
    }

    private void backtrack(List<String> result, StringBuilder current,
                           String digits, int index) {
        if (current.length() == digits.length()) {
            result.add(current.toString());
            return;
        }
        char digit = digits.charAt(index);
        String letters = digitToLetters.get(digit);
        for (char letter : letters.toCharArray()) {
            current.append(letter);
            backtrack(result, current, digits, index + 1);
            current.deleteCharAt(current.length() - 1);
        }
    }

}

知识点：

哈希

解题思路：

首先定义了数字到字母的映射 digitToLetters。然后，我们使用回溯算法来生成所有可能的牛名组合。在 letterCombinations 方法中，我们通过递归调用 backtrack 方法来生成组合。在 backtrack 方法中，我们根据当前数字找到对应的字母集合，然后对每个字母进行尝试，并递归地生成下一个位置的字母。最终，当生成的组合长度等于输入数字的长度时，我们将组合添加到结果列表中。