LeetCode 17 - Letter Combinations of a Phone Number

作者 QIFAN 日期 2017-02-10
LeetCode 17 - Letter Combinations of a Phone Number

原题链接: 17. Letter Combinations of a Phone Number


题干

给定一串数字,参照电话,返回所以可以组成的组合。

思路

遍历数组,传递当前的 digit 的位置,对每个位置都进行递归。若对应的数字无字母表示,直接返回。
base case 为 index 为末尾且字符串不为空,加入列表

我的这个数据结构选的太智障了,明明用数组就可以干的竟然用 map 。

代码:

public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return res;
}
Map<Character, char[]> map = new HashMap<>();
initialize(map);
StringBuilder s = new StringBuilder();
generate(digits, 0, s, map, res);
return res;
}
private void generate(String digits,
int index,
StringBuilder s,
Map<Character, char[]> map,
List<String> res) {
if (index == digits.length()) {
if (s.length() == 0) {
return;
}
res.add(s.toString());
return;
}
char digit = digits.charAt(index);
if (!map.containsKey(digit)) {
return;
}
for (int i = 0; i < map.get(digit).length; i++) {
generate(digits, index + 1, s.append(map.get(digit)[i]), map, res);
s.deleteCharAt(s.length() - 1);
}
}
private void initialize(Map<Character, char[]> map) {
char[] letter2 = {'a', 'b', 'c'};
map.put('2', letter2);
char[] letter3 = {'d', 'e', 'f'};
map.put('3', letter3);
char[] letter4 = {'g', 'h', 'i'};
map.put('4', letter4);
char[] letter5 = {'j', 'k', 'l'};
map.put('5', letter5);
char[] letter6 = {'m', 'n', 'o'};
map.put('6', letter6);
char[] letter7 = {'p', 'q', 'r', 's'};
map.put('7', letter7);
char[] letter8 = {'t', 'u', 'v'};
map.put('8', letter8);
char[] letter9 = {'w', 'x', 'y', 'z'};
map.put('9', letter9);
}