17. Letter Combinations of a Phone Number
class Solution {
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return res;
}
Map<Integer, String> map = new HashMap<>();
map.put(2, "abc");
map.put(3, "def");
map.put(4, "ghi");
map.put(5, "jkl");
map.put(6, "mno");
map.put(7, "pqrs");
map.put(8, "tuv");
map.put(9, "wxyz");
StringBuilder sb = new StringBuilder();
helper(digits, 0, sb, res, map);
return res;
}
private void helper(String digits, int index, StringBuilder sb, List<String> res, Map<Integer, String> map) {
if (index == digits.length()) {
res.add(sb.toString());
return;
}
// Subtract '0' from char to get an int
String letter = map.get(digits.charAt(index) - '0');
for (int i = 0; i < letter.length(); i++) {
sb.append(letter.charAt(i));
helper(digits, index + 1, sb, res, map);
sb.deleteCharAt(sb.length() - 1);
}
}
}
class Solution:
def letterCombinations(self, digits: 'str') -> 'List[str]':
digit_dict = {}
digit_dict['2'] = "abc"
digit_dict['3'] = "def"
digit_dict['4'] = "ghi"
digit_dict['5'] = "jkl"
digit_dict['6'] = "mno"
digit_dict['7'] = "pqrs"
digit_dict['8'] = "tuv"
digit_dict['9'] = "wxyz"
res = []
if not digits or len(digits) == 0:
return res
self.helper(digits, 0, digit_dict, "", res)
return res
def helper(self, digits, index, digit_dict, cur, res):
if index == len(digits):
res.append(cur)
return
cur_digit = digits[index]
cur_letter = digit_dict[cur_digit]
for j in range(len(cur_letter)):
self.helper(digits, index + 1, digit_dict, cur + cur_letter[j], res)