描述
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
解题思路
看到这道题想到的方法就是KMP算法了，但是一看难道归类为简单，其次也是因为不记得KMP的具体过程，无法手撕，最后还是决定直接遍历，暴力求解了。
代码如下：
class Solution {
public int strStr(String haystack, String needle) {
if (needle.equals("")) {
return 0;
}
if (haystack.equals("")) {
return -1;
}
char[] raw = haystack.toCharArray();
char[] need = needle.toCharArray();
for (int i = 0; i <=raw.length - need.length; i++) {
int j = 0;
while (j<need.length){
if (raw[i+j]!= need[j]){
j = -1;
break;
}else {
j++;
}
}
if (j == need.length) {
return i;
}
}
return -1;
}
}
运行结果：
10:52 info
解答成功:
执行耗时:1 ms,击败了71.21% 的Java用户
内存消耗:38.4 MB,击败了35.83% 的Java用户
题解
方法一：子串逐一比较 - 线性时间复杂度
最直接的方法 - 沿着字符换逐步移动滑动窗口，将窗口内的子串与 needle 字符串比较。
class Solution {
public int strStr(String haystack, String needle) {
int L = needle.length(), n = haystack.length();
for (int start = 0; start < n - L + 1; ++start) {
if (haystack.substring(start, start + L).equals(needle)) {
return start;
}
}
return -1;
}
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法二：双指针 - 线性时间复杂度
上一个方法的缺陷是会将 haystack 所有长度为 L 的子串都与 needle 字符串比较，实际上是不需要这么做的。
首先，只有子串的第一个字符跟 needle 字符串第一个字符相同的时候才需要比较
其次，可以一个字符一个字符比较，一旦不匹配了就立刻终止。
class Solution {
public int strStr(String haystack, String needle) {
int L = needle.length(), n = haystack.length();
if (L == 0) return 0;
int pn = 0;
while (pn < n - L + 1) {
// find the position of the first needle character
// in the haystack string
while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0)) ++pn;
// compute the max match string
int currLen = 0, pL = 0;
while (pL < L && pn < n && haystack.charAt(pn) == needle.charAt(pL)) {
++pn;
++pL;
++currLen;
}
// if the whole needle string is found,
// return its start position
if (currLen == L) return pn - L;
// otherwise, backtrack
pn = pn - currLen + 1;
}
return -1;
}
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法三： Rabin Karp - 常数复杂度
有一种最坏时间复杂度也为 O(N)O(N) 的算法。思路是这样的，先生成窗口内子串的哈希码，然后再跟 needle 字符串的哈希码做比较。
class Solution {
// function to convert character to integer
public int charToInt(int idx, String s) {
return (int)s.charAt(idx) - (int)'a';
}
public int strStr(String haystack, String needle) {
int L = needle.length(), n = haystack.length();
if (L > n) return -1;
// base value for the rolling hash function
int a = 26;
// modulus value for the rolling hash function to avoid overflow
long modulus = (long)Math.pow(2, 31);
// compute the hash of strings haystack[:L], needle[:L]
long h = 0, ref_h = 0;
for (int i = 0; i < L; ++i) {
h = (h * a + charToInt(i, haystack)) % modulus;
ref_h = (ref_h * a + charToInt(i, needle)) % modulus;
}
if (h == ref_h) return 0;
// const value to be used often : a**L % modulus
long aL = 1;
for (int i = 1; i <= L; ++i) aL = (aL * a) % modulus;
for (int start = 1; start < n - L + 1; ++start) {
// compute rolling hash in O(1) time
h = (h * a - charToInt(start - 1, haystack) * aL
+ charToInt(start + L - 1, haystack)) % modulus;
if (h == ref_h) return start;
}
return -1;
}
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
小结
双指针暴力求解效率还可以，但方法三更适合学习，KMP实现过于复杂，需要了解，但不是最优选择