Problem 17: Letter Combinations of a Phone Number
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
思路
排列模板
先把每个数字对应的字母存到 HashMap 里,然后不停地罗列不同的排列
public class Solution {
public List<String> letterCombinations(String digits) {
List<String> rst = new ArrayList<String>();
if (digits == null || digits.length() == 0) {
return rst;
}
HashMap<Character, char[]> map = new HashMap<Character, char[]>();
map.put('0', new char[]{});
map.put('1', new char[]{});
map.put('2', new char[]{'a', 'b', 'c'});
map.put('3', new char[]{'d', 'e', 'f'});
map.put('4', new char[]{'g', 'h', 'i'});
map.put('5', new char[]{'j', 'k', 'l'});
map.put('6', new char[]{'m', 'n', 'o'});
map.put('7', new char[]{'p', 'q', 'r', 's'});
map.put('8', new char[]{'t', 'u', 'v'});
map.put('9', new char[]{'w', 'x', 'y', 'z'});
StringBuilder sb = new StringBuilder();
helper(digits, map, sb, rst);
return rst;
}
private void helper(String digits, HashMap<Character, char[]> map, StringBuilder sb, List<String> rst) {
if (sb.length() == digits.length()) {
rst.add(sb.toString());
return;
}
for (char c : map.get(digits.charAt(sb.length()))) {
sb.append(c);
helper(digits, map, sb, rst);
sb.deleteCharAt(sb.length() - 1);
}
}
}
易错点
初始化数组
char[] arr = new char[] {'a', 'b', 'c'};
注意右边不要把 “[]” 丢了
helper 退出条件
if (sb.length() == digits.length()) { result.add(sb.toString()); return; }
核心的遍历部分
for (char c : map.get(digits.charAt(sb.length()))) { sb.append(c); helper(map, sb, digits, result); sb.deleteCharAt(sb.length() - 1); }
用
sb.length()
来 record digits 的每个字符,这个太厉害了!map.get()
是得到键对应的值;digits.charAt()
得到每一个数字;然后sb.length()
对应是第几个数字StringBuilder 的方法
StringBuilder sb = new StringBuilder(); sb.append('a'); sb.deleteCharAt(sb.length() - 1);
Follow Up
在面试的时候遇到了这道题,问到了一些数组初始化的问题
String 数组的初始化
String[] arr = new String[10];
String 数组初始化,每个数组内的元素都是
null
,与 int 数组是不同的int[] arr = new int[10];
int 数组初始化,每个数组内的元素为
0
StringBuilder 新建后是怎么样的?
StringBuilder sb = new StringBuider();
Last updated
Was this helpful?