17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

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"].

　　这里很容易想到要递归调用，直接给出代码如下：

    public  List<String> letterCombinations(String digits) {
        return getList(digits);
    }

    public static List<String> getList(String digits) {
        if (0 == digits.length()) {
            return new ArrayList<String>(0);
        } else if (1 == digits.length()) {
            return DICTIONARY.get(digits);
        } else {
            List<String> result = new ArrayList<String>();
            List<String> fristStr = DICTIONARY.get("" + digits.charAt(0));
            List<String> preResult = getList(digits.substring(1, digits.length()));
            for (String letter : fristStr) {
                for (String lett : preResult) {
                    result.add(letter + lett);
                }
            }
            return result;
        }
    }

    private static final Map<String, List<String>> DICTIONARY = new HashMap<String, List<String>>() {{
        put("0", Arrays.asList(""));
        put("1", Arrays.asList(""));
        put("2", Arrays.asList("a", "b", "c"));
        put("3", Arrays.asList("d", "e", "f"));
        put("4", Arrays.asList("g", "h", "i"));
        put("5", Arrays.asList("j", "k", "l"));
        put("6", Arrays.asList("m", "n", "o"));
        put("7", Arrays.asList("p", "q", "r", "s"));
        put("8", Arrays.asList("t", "u", "v"));
        put("9", Arrays.asList("w", "x", "y", "z"));
    }};

 　　最早的时候觉得写字典表麻烦，还萌萌哒的写了个函数生成字典（花费的时间更多），其实面对这一类固定的数据，不管从编码时间还是程序运行效率上来讲，直接写静态变量都是更好的选择。

　　private static HashMap<String, List<String>> getLetterMap() {
        HashMap<String, List<String>> letterMap = new HashMap<String, List<String>>();
        letterMap.put("0", new ArrayList<String>(0));
        letterMap.put("1", new ArrayList<String>(0));
        int letterIndex = 97;
        int index = 0;
        for (int i = 2; i < 10; i++) {
            List<String> letters = new ArrayList<String>();
            if (String.valueOf(i).equals("7") || String.valueOf(i).equals("9")) {
                index = 4;
            } else {
                index = 3;
            }
            for (int j = 0; j < index; j++) {
                letters.add(String.valueOf((char) letterIndex));
                letterIndex++;
            }
            letterMap.put(String.valueOf(i), letters);
        }
        return letterMap;
    }

　　提交后发现算法效率并不高，注意到

 List<String> preResult = getList(digits.substring(1, digits.length()));

　　这句即耗时间又耗空间，其实完全不用生成新的字符串，每次传入+1的index即可，作为递归结束条件。