/**
1. 每个案件代表多个字母, 所以遍历每一种可能性并记录
2. dfs:
    2.1 状态定义: 当前数字选择了哪个字母
    2.2 状态转移: 下一个数组选择了哪个字母
    2.3 判断退出: 所有数字遍历完成

*/

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        if(digits == null || digits.length() == 0) return result;

        dfs(digits, 0, result, new StringBuilder(), initMap());

        return result;
    }

    void dfs(String digits, int index, List<String> result, StringBuilder buffer, Map<Character, String> map) {
        if (index == digits.length()) {
            result.add(buffer.toString());
            return ;
        }

        String candidate = map.get(digits.charAt(index));
        for (int i = 0 ; i < candidate.length(); i++) {
            buffer.append(candidate.charAt(i));
            dfs(digits, index+1, result, buffer, map);
            buffer.setLength(buffer.length()-1);
        }
    }

    Map<Character, String> initMap() {
        Map<Character, 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");
        return map;
    }
}

version: 2020-03-06

/*
映射后爆搜即可
*/

class Solution {

    String[] mapping = initMapping();
    Set<String> res = new HashSet<>();
    StringBuilder buffer = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        dfs(digits, 0);
        return new ArrayList<String>(res);
    }

    void dfs(String digits, int cur){
        if (cur == digits.length()){
            if (buffer.length() != 0) res.add(buffer.toString());
            return;
        }

        int index = digits.charAt(cur) - '0';
        for (int i = 0 ; i <  mapping[index].length(); i++){
            char c =  mapping[index].charAt(i);
            buffer.append(c);
            dfs(digits, cur+1);
            buffer.setLength(buffer.length()-1);
        }

    }

    private String[] initMapping(){
        String[] map = new String[10];
        map[2] = "abc";
        map[3] = "def";
        map[4] = "ghi";
        map[5] = "jkl";
        map[6] = "mno";
        map[7] = "pqrs";
        map[8] = "tuv";
        map[9] = "wxyz";
        return map;
    }
}