Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, 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.

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

Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution:

class Solution {
    public List<String> letterCombinations(String digits) {
        Map<Character, List<Character>> map = new HashMap<>();
        map.put('2', Arrays.asList('a', 'b', 'c'));
        map.put('3', Arrays.asList('d', 'e', 'f'));
        map.put('4', Arrays.asList('g', 'h', 'i'));
        map.put('5', Arrays.asList('j', 'k', 'l'));
        map.put('6', Arrays.asList('m', 'n', 'o'));
        map.put('7', Arrays.asList('p', 'q', 'r', 's'));
        map.put('8', Arrays.asList('t', 'u', 'v'));
        map.put('9', Arrays.asList('w', 'x', 'y', 'z'));
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) return result;
        List<List<Character>> list = new ArrayList<>();
        for (char c : digits.toCharArray()) {
            list.add(map.get(c));
        }
        backtrack(result, new StringBuilder(), list);
        return result;
    }
    
    private void backtrack(List<String> result, StringBuilder sb, List<List<Character>> list) {
        if (sb.length() == list.size()) {
            result.add(sb.toString());
            return;
        }
        int level = sb.length();
        List<Character> set = list.get(level);
        for (char c : set) {
            sb.append(c);
            backtrack(result, sb, list);
            sb.setLength(sb.length() - 1);
        }
    }
}