# 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.

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);
}

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();
}
}
}
``````