Given a string containing digits from 2-9 inclusive,
return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
2 -> abc
3 -> def
4 -> ghi
5 -> jkl
6 -> mno
7 -> pqrs
8 -> tuv
9 -> wxyz
Test Cases
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Solution
class Solution {
public List<String> letterCombinations(String digits) {
Map<Integer, List<Character>> phone = new HashMap<>();
phone.put(2, Arrays.asList('a', 'b', 'c'));
phone.put(3, Arrays.asList('d', 'e', 'f'));
phone.put(4, Arrays.asList('g', 'h', 'i'));
phone.put(5, Arrays.asList('j', 'k', 'l'));
phone.put(6, Arrays.asList('m', 'n', 'o'));
phone.put(7, Arrays.asList('p', 'q', 'r', 's'));
phone.put(8, Arrays.asList('t', 'u', 'v'));
phone.put(9, Arrays.asList('w', 'x', 'y', 'z'));
List<String> result = new ArrayList<>();
if (digits.length() == 0) return result;
generate(digits, 0, phone, result, new StringBuilder());
return result;
}
private void generate(String digits, int pos, Map<Integer, List<Character>> phone, List<String> result, StringBuilder sb) {
if (sb.length() == digits.length()) {
result.add(sb.toString());
return;
}
int digit = digits.charAt(pos) - '0';
for(Character c: phone.get(digit)) {
sb.append(c);
generate(digits, pos+1, phone, result, sb);
sb.deleteCharAt(sb.length() - 1);
}
}
}