17. Letter Combinations of a Phone Number (Medium)

https://leetcode.com/problems/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.

Example:

Input: "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.

Solutions

class Solution {

    private List<String> ans = new ArrayList<>();

    // Keep the map between digits and letters
    private Map<Integer, List<Character>> digitMap = new HashMap<>();

    // Keep track of the possible combination of the letters
    private Stack track = new Stack();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return ans;
        }

        for (int i = 0; i < 8; i++) {
            digitMap.put(i + 2, new ArrayList<>());
        }

        for (int i = 0; i < 6; i++) {
            int base = 'a' + i * 3;

            Character c0 = Character.valueOf((char) (base + 0));
            Character c1 = Character.valueOf((char) (base + 1));
            Character c2 = Character.valueOf((char) (base + 2));

            digitMap.get(i + 2).addAll(Arrays.asList(new Character[]{c0, c1, c2}));
        }

        // Letters on 7, 8, 9 are different, should be treated separately.
        digitMap.get(7).add('s');

        digitMap.get(8).add('t');
        digitMap.get(8).add('u');
        digitMap.get(8).add('v');

        digitMap.get(9).add('w');
        digitMap.get(9).add('x');
        digitMap.get(9).add('y');
        digitMap.get(9).add('z');

        recurse(digits, 0);

        return ans;
    }

    private void recurse(String digits, int idx) {
        if (idx == digits.length()) {
            String rst = "";
            for (int i = 0; i < track.size(); i++) {
                rst += track.get(i);
            }

            ans.add(rst);
            return;
        }

        int dig = digits.charAt(idx) - '0';
        if (!digitMap.containsKey(dig)) {
            return;
        }

        List<Character> chars = digitMap.get(dig);
        for (Character c : chars) {
            track.push(c);
            recurse(digits, idx + 1);
            track.pop();
        }
    }
}

Incorrect Solutions

References