记录生活中的点点滴滴

0%

leetcode17:电话号码的字母组合

记录一下下面这道题的求解,两种方法:回溯法、迭代取余求解法

17. 电话号码的字母组合

先说一下常规的回溯的思想求解:先定义一个map,其实这题直接定义一个数组即可,因为根据下标就能找到对应的字符串,然后通过字符串的长度进行迭代回溯dfs。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
String[] str = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
List<String> list = new ArrayList<>();
public List<String> letterCombinations(String digits) {
char[] arr = digits.toCharArray();
int n = arr.length;
if(n==0)return list;
backtrack(arr,"",0);
return list;
}
public void backtrack(char[] arr,String s,int i){
int n = arr.length;
if(n==i){
list.add(s);
return;
}
char[] cs = str[arr[i]-'2'].toCharArray();
int len = cs.length;
for(int j=0;j<len;j++){
String t = s+cs[j];
backtrack(arr,t,i+1);
}
}
}

这种方法是常规的回溯算法,击败时间率为23%,下面看看另一种方法:

还有一种牛逼的方法,就是先求解出有多少种解法,比如上面的例子:

1
2
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

23的话,有3*3=9种情况,然后下标i即0 1 2 3 4 5 6 7 8,通过这个去迭代23的两个位,i先对第一位取余,然后除以第一位的长度,对第二位取余,除以第二位的长度,依次类推。。。

对于每一次i,都能确认出每一位不同的字符,然后拼接,得到不同的字符串,集合添加字符串。

迭代完毕,最终也添加完毕!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if(digits == null || digits.length() == 0){
return result;
}
int n = digits.length();
String[] strs = new String[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
//1.先算出一共有几种
int len = 1;
for(int i = 0; i < n; i++){
int c = digits.charAt(i)-'2';
len *= strs[c].length();
}
//再用求余方法拿到每一种
for(int i = 0 ; i < len; i++){
int last = i;
StringBuilder sb = new StringBuilder();
for(int j=0;j<n;j++){
int c = digits.charAt(j)-'2';
int p
os = last%strs[c].length();
sb.append(strs[c].charAt(pos));
last/=strs[c].length();
}
result.add(sb.toString());
}
return result;
}
}

这种方法就厉害了,击败100%。

我也是看大佬的题解才发现这种解法的,感觉应该也可以应用到其他的题中!