LeetCode-Implement strStr()

https://leetcode-cn.com/problems/implement-strstr/

最开始的思路:循环被比较字符串,当第一个元素和匹配字符串一样的时候,继续比较。另外就是需要再开始处理一些异常输入。

结果用时真的太长了,1285 ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int strStr(String haystack, String needle) {
if(needle.length()>haystack.length())
return -1;
if(needle.length()==0)
return 0;
for(int i=0;i<haystack.length();i++){
if(haystack.charAt(i)==needle.charAt(0)){
Boolean finish=true;
for(int j=0;j<needle.length();j++){
if((i+j+1)>haystack.length() || haystack.charAt(i+j)!=needle.charAt(j)){
finish=false;
break;
}
}
if(finish)
return i;
}
}
return -1;
}
}

将思路进行优化,用两个指针的移动代替两层循环,用时少了很多,只用了 7ms,超过了 43.24%的人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int strStr(String haystack, String needle) {
if(needle.length()>haystack.length())
return -1;
if(needle.length()==0)
return 0;
int hay_pos=0;
int need_pos=0;
while(hay_pos<haystack.length()){
if(haystack.charAt(hay_pos)==needle.charAt(need_pos)){
hay_pos++;
need_pos++;
if(need_pos==needle.length()){
return hay_pos-need_pos;
}
}else{
hay_pos=hay_pos-need_pos+1;
need_pos=0;
}
}
return -1;
}
}

但这还不是最优解。因为。最开始苦思冥想,想到可以参考之前匹配的串,在匹配失败后不回溯太多,但是如果使用几个变量的话,在很多情况下都会有 bug,感觉记录的信息太少,需要用数组记录,但是没想清楚如何记录。

最后想到之前在数据结构中学习过 KMP 算法(当时也没怎么搞懂),所以在参考了KMP 算法的基本原理Next 数组的生成方法,以及KMP ~~从入门到理解到彻底理解以后,书写代码如下:

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
31
32
class Solution {
public int[] getNext(String needle){
int[] next=new int[needle.length()];
next[0]=-1;
int k=-1;
for(int i=1;i<needle.length();i++){
while(k>-1 && needle.charAt(k+1)!=needle.charAt(i))
k=next[k];
if(needle.charAt(k+1)==needle.charAt(i))
k++;
next[i]=k;
}
return next;
}
public int strStr(String haystack, String needle) {
if(needle.length()>haystack.length())
return -1;
if(needle.length()==0)
return 0;
int[] next=getNext(needle);
int k=-1;
for(int i=0;i<haystack.length();i++){
while(k>-1 && haystack.charAt(i)!=needle.charAt(k+1))
k=next[k];
if(haystack.charAt(i)==needle.charAt(k+1))
k++;
if(k+1==needle.length())
return i-needle.length()+1;
}
return -1;
}
}

最后只超过了 23.8%的人,还比之前慢了,分析可能是测试用例里有重复的串太少,而且串比较短导致的。