电话号码的字母组合

2020-12-11

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

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

static Map<Character, List<Character>> d2AMap = new HashMap<>();

d2AMap.put('2', Arrays.asList('a', 'b', 'c'));
d2AMap.put('3', Arrays.asList('d', 'e', 'f'));
d2AMap.put('4', Arrays.asList('g', 'h', 'i'));
d2AMap.put('5', Arrays.asList('j', 'k', 'l'));
d2AMap.put('6', Arrays.asList('m', 'n', 'o'));
d2AMap.put('7', Arrays.asList('p', 'q', 'r', 's'));
d2AMap.put('8', Arrays.asList('t', 'u', 'v'));
d2AMap.put('9', Arrays.asList('w', 'x', 'y', 'z'));

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

最暴力的回溯

class Solution {

    
    static Map<Character, List<Character>> d2AMap = new HashMap<>();
    List<String> result = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits.equals("")){
            return new ArrayList<String>();
        }
        d2AMap.put('2', Arrays.asList('a', 'b', 'c'));
        d2AMap.put('3', Arrays.asList('d', 'e', 'f'));
        d2AMap.put('4', Arrays.asList('g', 'h', 'i'));
        d2AMap.put('5', Arrays.asList('j', 'k', 'l'));
        d2AMap.put('6', Arrays.asList('m', 'n', 'o'));
        d2AMap.put('7', Arrays.asList('p', 'q', 'r', 's'));
        d2AMap.put('8', Arrays.asList('t', 'u', 'v'));
        d2AMap.put('9', Arrays.asList('w', 'x', 'y', 'z'));
        backtrack(0, digits, new StringBuilder());
        return result;
    }

    public void backtrack(int cur, String digits, StringBuilder bd) {
        if (cur == digits.length()) {
            result.add(bd.toString());
        } else {
            List<Character> list = d2AMap.get(digits.charAt(cur));
            for (int i = 0; i < list.size(); i++) {
                bd.append(list.get(i));
                backtrack(cur + 1, digits, bd);
                bd.deleteCharAt(bd.length() - 1);
            }

        }

    }
}

官方题解


class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

时间复杂度：O(3^m \times 4^n)其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9），m+n 是输入数字的总个数。当输入包含 m 个对应 3 个字母的数字和 nn 个对应 44 个字母的数字时，不同的字母组合一共有 3^m \times 4^n种，需要遍历每一种字母组合。

空间复杂度：O(m+n)，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n 是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+n。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。