LeetCode28. Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

1
2
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2
Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf()).


暴力搜索

思路

  1. 如果是pattern是空,返空。
  2. 如果pattern比text还要长,返-1。
  3. 从text的0开始遍历,一直到text剩下的字符串等于pattern的时候为止。不用遍历到text的末尾,这样可以提高效率。

My code in cpp

naive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int strStr(string haystack, string needle) {
int p = needle.size(), t = haystack.size();
if (!p) return 0;
if (p>t) return -1;
for (int index = 0; index <= t - p; index++)
{
for (int i=index,j = 0; j < p; j++,i++)
{
if (haystack[i] != needle[j])
break;
if (j == p-1)
return index;
}
}
return -1;
}

KMP算法

coming soon~~

总结

  1. 字符串匹配问题
  2. 暴力搜索法 O(m*n)
  3. KMP算法O(m+n)
Thanks for Support.