leetcode算法--电话号码的字母组合

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。^[1]

输入法
示例:

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

二、解题思路

因为不知道数字字符串长度，所以无法判断几重for循环，自然想到使用递归的方法

1. 如果只有1个数字，则返回对应的字母列表
2. 如果有2个数字，则将两个字母列表两两结合，并返回结果
3. 如果有3个数字，按照步骤2获取前2个数字字母组合，再将结果和第3个数字对应的字母列表进行两两组合，返回最终结果
4. 如果有4个数字，则按照步骤3获取前3个数字字母组合，在将结果和第4个数字对应的字符列表两两结合，返回最终结果
   以此类推......

三、代码

1. 先初始化数字与字母列表的映射关系

    public static final Map<String, List<String>> NUMBER2LETTERS_MAP = new HashMap<>();

    static {
        List<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("b");
        list2.add("c");
        NUMBER2LETTERS_MAP.put("2", list2);

        List<String> list3 = new ArrayList<>();
        list3.add("d");
        list3.add("e");
        list3.add("f");
        NUMBER2LETTERS_MAP.put("3", list3);

        List<String> list4 = new ArrayList<>();
        list4.add("g");
        list4.add("h");
        list4.add("i");
        NUMBER2LETTERS_MAP.put("4", list4);

        List<String> list5 = new ArrayList<>();
        list5.add("j");
        list5.add("k");
        list5.add("l");
        NUMBER2LETTERS_MAP.put("5", list5);

        List<String> list6 = new ArrayList<>();
        list6.add("m");
        list6.add("n");
        list6.add("o");
        NUMBER2LETTERS_MAP.put("6", list6);

        List<String> list7 = new ArrayList<>();
        list7.add("p");
        list7.add("q");
        list7.add("r");
        list7.add("s");
        NUMBER2LETTERS_MAP.put("7", list7);

        List<String> list8 = new ArrayList<>();
        list8.add("t");
        list8.add("u");
        list8.add("v");
        NUMBER2LETTERS_MAP.put("8", list8);

        List<String> list9 = new ArrayList<>();
        list9.add("w");
        list9.add("x");
        list9.add("y");
        list9.add("z");
        NUMBER2LETTERS_MAP.put("9", list9);
    }

2. 递归计算

public List<String> letterCombinations(String digits) {
    if (digits.length() <= 1) {
        return NUMBER2LETTERS_MAP.getOrDefault(digits, new ArrayList<>());
    }
    String lastNumber = String.valueOf(digits.charAt(digits.length() - 1));
    List<String> lastList = NUMBER2LETTERS_MAP.get(lastNumber);
    List<String> preList = letterCombinations(digits.substring(0, digits.length() - 1));
    List<String> combinationList = new ArrayList<>(lastList.size() * preList.size());
    for (String preCombination : preList) {
        for (String lastLetter : lastList) {
            combinationList.add(preCombination + lastLetter);
        }
    }
    return combinationList;
}

---

1. 17. 电话号码的字母组合- 力扣（LeetCode） ↩