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