17_letterCombinations.java

public class Solution {
    public List<String> letterCombinations(String digits) {
        HashMap<Integer, char[]> map = new HashMap<Integer, 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'});
        
        
        List<String> result = new ArrayList<String>();
        if(digits == null || digits.length() == 0) return result;
        int len = digits.length();
        
        dfs(digits, result, len, 0, map, "");
        return result;
    }
    
    public void dfs(String digits, List<String> result, int len, int k, HashMap<Integer, char[]> map, String current){
        if(k == len){
            result.add(current);
            return;
        }
        int num = digits.charAt(k)-'0';
        char[] arr = map.get(num);
        for(char c : arr){
            dfs(digits, result, len, k+1, map, current+c);
        }
    }
}