17. Letter Combinations of a Phone Number

1.典型的dfs，hashmap中存放char会比string快一些。一开始的解法，代码/传参很多，较为麻烦。

class Solution {

    // set map as static variable 
    static Map<Character, String> map = new HashMap<>();

    public List<String> letterCombinations(String digits) {
        // boundary check 
        if (digits == null || digits.length() == 0) return new ArrayList<>();

        // fill map
        createMap(map);

        // generate key list
        char[] keys = digits.toCharArray();

        // generate strings
        List<String> res = new ArrayList<>();
        StringBuffer path = new StringBuffer();
        dfs(keys, res, path, 0);
        return res;
    }

    private void dfs(char[] keys, List<String> res, StringBuffer path, int index) {
        if (index == keys.length) {
            res.add(path.toString());
            return;
        }
        char key = keys[index];
        if (!map.containsKey(key)) return;
        String letters = map.get(key);
        for (int i = 0; i < letters.length(); i++) {
            path.append(letters.charAt(i));
            dfs(keys, res, path, index + 1);
            path.setLength(path.length() - 1);
        }
    }

    private void createMap(Map<Character, String> map) {
        map.put('0', " ");
        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");
    }
}

2.然后是字符串原生操作，比较快，但是需要习惯char取index

class Solution {
    String[] map = {" ",    //0
                    "",     //1
                    "abc",  //2
                    "def",  //3
                    "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        // boundary check 
        if (digits == null || digits.length() == 0) return new ArrayList<>();

        // get key list
        char[] keys = digits.toCharArray();

        List<String> res = new ArrayList<>();
        dfs(keys, res, "", 0);
        return res;
    }

    private void dfs(char[] keys, List<String> res, String path, int index) {
        if (index == keys.length) {
            res.add(path);
            return;
        }
        char key = keys[index]; // 2 or 3
        String letters = map[key - '0']; // remember this fucking shit
        for (int i = 0; i < letters.length(); i++) {
            // a convenient way to debug
            System.out.println(index + " use: " + letters.charAt(i) + " get:" + s + letters.charAt(i));
            dfs(keys, res, path + letters.charAt(i), index + 1);
        }
    }
}

边界考虑，对于特殊字符串，hashmap比较方便。leetcode测试中0不是空格而是返回空，所以0加不加都可以。

""
"0"
"()*&"

print debug大法

0 use: a get:a
1 use: d get:ad
1 use: e get:ae
1 use: f get:af
0 use: b get:b
1 use: d get:bd
1 use: e get:be
1 use: f get:bf
0 use: c get:c
1 use: d get:cd
1 use: e get:ce
1 use: f get:cf
[ad, ae, af, bd, be, bf, cd, ce, cf]