17.Letter Combinations of a Phone Number

Given a string containing digits from2-9inclusive, 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. Note that 1 does not map to any letters.

Example:

Input: 
"23"

Output:
 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Initial solution by Bruteforce

class Solution {
    Map<Character, String> map = new HashMap<>();
    public List<String> combination(String digits, int idx) {
        List<String> list = new ArrayList<>();
        if (idx == digits.length()-1) {
            char[] letters = map.get(digits.charAt(idx)).toCharArray();
            for (char letter : letters)
                list.add(String.valueOf(letter));
        } else {
            List<String> pList = combination(digits, idx+1);
            char[] letters = map.get(digits.charAt(idx)).toCharArray();
            for (char letter : letters) {
                for (String s : pList) {
                    list.add(letter + s);
                }
            }
        }
        return list;
    }
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return new ArrayList<String>();
        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 combination(digits, 0);
    }
}

Second solution by backtracking (check this)

class Solution {
    String[] phoneMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        List<String> resultList = new ArrayList<>();
        if (digits.isEmpty()) return resultList;
        StringBuilder sb = new StringBuilder();
        helper(digits, 0, resultList, sb);
        return resultList;
    }

    public void helper(String digits, int index, List<String> resultList, StringBuilder sb) {
        if (sb.length() == digits.length()) {
            resultList.add(sb.toString());
            return;
        }
        char[] letters = phoneMap[Character.getNumericValue(digits.charAt(index))].toCharArray();
        // or char[] letters = phoneMap[(int)(digits.charAt(index)-'0')].toCharArray();
        for (char c : letters) {
            sb.append(c);
            helper(digits, index+1, resultList, sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}