题解 | #牛名生成器#

一、知识点：

哈希、递归、遍历

二、文字分析：

1. 创建一个结果列表 result，用于存储所有可能的牛名组合。
2. 创建一个字符串 curr，用于构建当前的牛名组合。
3. 使用递归函数 backtrack 生成所有可能的组合：如果 curr 的长度等于 digits 的长度，说明已经完成一种组合，将 curr 添加到结果列表中。如果 curr 的长度小于 digits 的长度，取出当前数字对应的字母串 letters。遍历 letters 的每个字符 ch，将 ch 连接到 curr 的末尾，并调用递归函数 backtrack。在递归函数结束后，将 curr 的末尾字符移除，回溯到上一个状态。
4. 返回结果列表。

三、编程语言：

java

四、正确代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    private static 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");
    }

    public String[] letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.length() == 0) {
            return result.toArray(new String[0]);
        }

        backtrack(digits, 0, new StringBuilder(), result);

        return result.toArray(new String[0]);
    }

    private void backtrack(String digits, int index, StringBuilder curr, List<String> result) {
        if (curr.length() == digits.length()) {
            result.add(curr.toString());
            return;
        }

        char digit = digits.charAt(index);
        String letters = digitToLetters.get(digit);

        for (char ch : letters.toCharArray()) {
            curr.append(ch);
            backtrack(digits, index + 1, curr, result);
            curr.deleteCharAt(curr.length() - 1);
        }
    }
}