实现strStr()

LeetCode题目,28. Implement strStr()

先看题目描述

skxDbD.png

大意就是给定一个 haystack 字符串和一个 needle 字符串,让我们在 haystack 字符串中找出 needle 字符串出现的第一个位置,如果不存在,则返回 -1

算法和思路

这题是一道典型的子串匹配问题,解决子串匹配问题比较经典的算法有 KMP算法,Sunday算法等,核心思路就是尽量增大模式串的移动步数,核心思路是这个,具体实现看下面代码吧,下面的代码实现的是 Sunday 算法

算法和源码

Sunday算法

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public int strStr(String haystack, String needle) {
int n = needle.length();
if (n == 0) {
return 0;
}
int m = haystack.length();
if (m < n) {
return -1;
}
char[] hs = haystack.toCharArray();
char[] ns = needle.toCharArray();
int[] offest = new int[26];
for (int i = 0; i < 26; i++) {
for (int j = n - 1; j >= 0; j--) {
if (ns[j] - 'a' == i) {
offest[i] = n - j;
break;
}
}
}
int start = 0;
while (start <= m - n && hs[start] != ns[0]) {
start++;
}
while (start <= m - n) {
int i = 0;
for (; i < n; i++) {
if (hs[i + start] != ns[i]) {
break;
}
}
if (i == n) {
return start;
}
int index = start + n;
if (index >= m) {
return -1;
}
char c = hs[index];
if (offest[c - 'a'] > 0) {
start += offest[c - 'a'];
} else {
start = index + 1;
while (start <= m - n && hs[start] != ns[0]) {
start++;
}
}
}
return -1;
}
}

因为这道题我第一反应是拿 Sunday 算法做,然后手写了个 Sunday 算法提交的,所以我还疑惑这题为什么是个简单题,后来看了别人的代码,发现可以直接调用内置函数,嗯那么这确实是道简单题

1
2
3
4
5
class Solution {
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle);
}
}