Leetcode 28 - Implement strStr()

Note:

  • Naive method: Start checking once haystack[i] === needle[0].
  • KMP continue

Question:

Implement strStr().

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

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().

Example:

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

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
if (needle.length === 0) return 0;
for (let i = 0; i < haystack.length; i++) {
if (haystack[i] === needle[0]) {
let j = i;
let k = 0;
while(j < haystack.length && k < needle.length) {
if (haystack[j] !== needle[k]) break;
j++;
k++;
}
if (k === needle.length) return i;
}
}
return -1;
};