问题链接

17. 电话号码的字母组合

问题描述

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

示例

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

输入：digits = "2"
输出：["a","b","c"]

解题思路

1. 迭代枚举所有可能
   这个没啥好说的，就是穷举。
2. 回溯枚举所有可能
   回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。

代码示例（JAVA）

1. 迭代

class Solution {
    public static List<String> letterCombinations(String digits) {
        if ("".equals(digits)) {
            return new ArrayList<>();
        }
        // 将数字到字母的映射保存到哈希表
        Map<Integer, String> map = new HashMap<>();
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "tuv");
        map.put(9, "wxyz");

        List<String> ans = new ArrayList<>();
        ans.add("");
        char[] chars = digits.toCharArray();
        for (int i = 0; i <= chars.length - 1; i++) {
            // 复制ans
            List<String> temp = new ArrayList<>(ans);
            ans.clear();

            String curString = map.get(chars[i] - '0');
            char[] arr = curString.toCharArray();
            for (int j = 0; j <= arr.length - 1; j++) {
                List<String> itemList = new ArrayList<>();
                for (String t : temp) {
                    itemList.add(t + arr[j]);
                }
                ans.addAll(itemList);
            }
        }
        return ans;
    }
}

2. 回溯

class Solution {
    public List<String> letterCombinations(String digits) {
        if ("".equals(digits)) {
            return new ArrayList<>();
        }
        // 将数字到字母的映射保存到哈希表
        Map<Integer, String> map = new HashMap<>();
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "tuv");
        map.put(9, "wxyz");

        List<String> ans = new ArrayList<>();
        recursion(new StringBuilder(""), digits, map, ans, 0);
        return ans;
    }

    public void recursion(StringBuilder s, String digits, Map<Integer, String> map, List<String> ans, int index) {
        if (index == digits.length()) {
            ans.add(s.toString());
            return;
        }

        String letters = map.get(digits.toCharArray()[index] - '0');
        for (char c : letters.toCharArray()) {
            recursion(s.append(c), digits, map, ans, index + 1);
            s.deleteCharAt(index);
        }
    }
}