[Leetcode] Letter Combinations of a Phone Number

Given a digit string, 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.

Input:Digit string "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.

DFS的模板题。

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<String>();
        String[][] 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"}};
        dfs(digits, 0, "", map, result);
        return result;
    }
    
    private void dfs(String digits, int ind, String current, String[][] map, List<String> result) {
        if(ind == digits.length()) {
            result.add(current);
        }
        else {
            int num = digits.charAt(ind) - '0';
            for(int i = 0; i < map[num].length; i++) {
                dfs(digits, ind+1, current+map[num][i], map, result);
            }
        }
    }