LeetCode17: 电话号码的字母组合

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

image.png

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

解题思路：这里我首先想到用hashmap简单暴力地存储数字到字母之间的映射关系，然后再采用一个递归函数，递归生成所有可能。递归地结束条件就是字符串遍历完毕地时候，这时添加到List String中。

package leetcode;

import java.util.*;

public class LetterCombinations {
    static Map<Character, List<String>> letters = new HashMap<>();
    static List<String> results = new ArrayList<>();
    static String source;

    public List<String> letterCombinations(String digits) {
        source = digits;
        letters.clear();
        results.clear();
        if (digits.equals("")) return results;
        letters.put('2', Arrays.asList("a", "b", "c"));
        letters.put('3', Arrays.asList("d", "e", "f"));
        letters.put('4', Arrays.asList("g", "h", "i"));
        letters.put('5', Arrays.asList("j", "k", "l"));
        letters.put('6', Arrays.asList("m", "n", "o"));
        letters.put('7', Arrays.asList("p", "q", "r", "s"));
        letters.put('8', Arrays.asList("t", "u", "v"));
        letters.put('9', Arrays.asList("w", "x", "y", "z"));

        putLetter(0, "");
        return results;
    }

    private void putLetter(int idx, String tmp) {
        if (idx == source.length()) {
            results.add(tmp);
            return;
        }
        for (String s : letters.get(source.charAt(idx))) {
            putLetter(idx + 1, tmp + s);
        }
    }
}