Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

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.

用一个HashMap存好对应关系，然后DFS。

public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        HashMap<Integer, char[]> map = new HashMap<Integer, char[]>();
        map.put(0, new char[]{});
        map.put(1, new char[]{});
        map.put(2, new char[]{'a','b','c'});
        map.put(3, new char[]{'d','e','f'});
        map.put(4, new char[]{'g','h','i'});
        map.put(5, new char[]{'j','k','l'});
        map.put(6, new char[]{'m','n','o'});
        map.put(7, new char[]{'p','q','r','s'});
        map.put(8, new char[]{'t','u','v'});
        map.put(9, new char[]{'w','x','y','z'});
        combination(digits, map, res, 0, "");
        return res;
    }
    
    private void combination(String digits, HashMap<Integer, char[]> map,
                             ArrayList<String> res, int index, String s) {
        if (index == digits.length()) {
            res.add(s);
            return;
        }          
        
        char[] candidate = map.get(digits.charAt(index) - '0');
        for (int i = 0; i < candidate.length; i++) {
            combination(digits, map, res, index + 1, s + candidate[i]);
        }
    }
}