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%的人，还比之前慢了，分析可能是测试用例里有重复的串太少，而且串比较短导致的。