Description

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

solution 1

一看题干，很明显是组合问题。没有想到很好的解决方法，先暴力解决。

    private static final char[][] map = {{},{'a','b','c'},{'d','e','f'}
        ,{'g','h','i'},{'j','k','l'},{'m','n','o'}
        ,{'p','q','r', 's'},{'t','u','v'},{'w','x','y', 'z'}};
    

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return new ArrayList<>();
        }
        List<List<String>> result = new ArrayList<>();
        for (int i = 0; i < digits.length(); i++) { 
            if (result.size() == 0) {
                List<String> list = new ArrayList<>();
                for (char c : map[digits.charAt(i) - '1']) {
                    list.add(String.valueOf(c));
                }
                result.add(list);
            } else {
                List<String> list = new ArrayList<>();
                for (char c : map[digits.charAt(i) - '1']) {
                    for (String s : result.get(i - 1)) {
                        list.add(new StringBuilder(s).append(c).toString());
                    }
                }
                result.add(list);
            }
        }
        return result.get(digits.length() - 1);
    }

粗略一看，复杂度大概是 $O(3^n)$ 。