Letter Phone

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.

The digit 0 maps to 0 itself.
The digit 1 maps to 1 itself.

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

Make sure the returned strings are lexicographically sorted.

Method:

Like combinations, except we use the list based on what letter it is.

Solution:

Time: O(4^n)
Space: (4^n)

public class Solution {
    public ArrayList<String> letterCombinations(String A) {
        Map<Character, List<Character>> map = new HashMap<>();
        map.put('0', Arrays.asList('0'));
        map.put('1', Arrays.asList('1'));
        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'));
        ArrayList<String> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        char[] arr = A.toCharArray();
        helper(arr, result, map, sb, 0);
        return result;
    }
    
    private void helper(char[] arr, ArrayList<String> result, Map<Character, List<Character>> map, StringBuilder sb, int digitIndex) {
        if (sb.length() == arr.length) {
            result.add(sb.toString());
            return;
        }
        List<Character> list = map.get(arr[digitIndex]);
        for (int i = 0; i < list.size(); i ++) {
            char letter = list.get(i);
            sb.append(letter);
            helper(arr, result, map, sb, digitIndex + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}