题解 | #牛名生成器#

知识点：哈希表，回溯

这道题目考查的主要是回溯算法，用到哈希表的地方在于我们需要找到数字和字母的对应关系。

首先，需要使用hashmap存储数字和字母的对应关系，然后，在根据出现的字符，依次尝试可能出现的字母，并保存下来，待所有数字遍历结束后，将该种字母排列保存下来。每次遍历结束后，需要删除当前字母，替换为下一个可能的字母。

Java题解如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param digits string字符串 
     * @return string字符串一维数组
     */
    private List<String> list = new ArrayList<>();
    private String digits;
    private Map<Character, char[]> map = new HashMap<>();

    public String[] letterCombinations (String digits) {
        // write code here
        if(digits.length() == 0) {
            return new String[0];
        }
        this.digits = digits;
        map.put('2', new char[]{'a', 'b', 'c'});
        map.put('3', new char[]{'d', 'e', 'f'});
        map.put('4', new char[]{'g', 'h', 'i'});
        map.put('5', new char[]{'j', 'k', 'l'});
        map.put('6', new char[]{'m', 'n', 'o'});
        map.put('7', new char[]{'p', 'q', 'r', 's'});
        map.put('8', new char[]{'t', 'u', 'v'});
        map.put('9', new char[]{'w', 'x', 'y', 'z'});
        backTracking(new StringBuilder(), 0);
        String[] res = new String[list.size()];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void backTracking(StringBuilder sb, int index) {
        if(index == digits.length()) {
            list.add(sb.toString());
            return;
        }
        for(char letter: map.get(digits.charAt(index))) {
            sb.append(letter);
            backTracking(sb, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}