Description#
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
Constraints:
1 <= haystack.length, needle.length <= 104haystack and needle consist of only lowercase English characters.
Solutions#
Solution 1: Traversal#
We compare the string needle with each character of the string haystack as the starting point. If we find a matching index, we return it directly.
Assuming the length of the string haystack is $n$ and the length of the string needle is $m$, the time complexity is $O((n-m) \times m)$, and the space complexity is $O(1)$.
1
2
3
4
5
6
7
| class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n, m = len(haystack), len(needle)
for i in range(n - m + 1):
if haystack[i : i + m] == needle:
return i
return -1
|
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
| class Solution {
public int strStr(String haystack, String needle) {
if ("".equals(needle)) {
return 0;
}
int len1 = haystack.length();
int len2 = needle.length();
int p = 0;
int q = 0;
while (p < len1) {
if (haystack.charAt(p) == needle.charAt(q)) {
if (len2 == 1) {
return p;
}
++p;
++q;
} else {
p -= q - 1;
q = 0;
}
if (q == len2) {
return p - q;
}
}
return -1;
}
}
|
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
| class Solution {
private:
vector<int> Next(string str) {
vector<int> n(str.length());
n[0] = -1;
int i = 0, pre = -1;
int len = str.length();
while (i < len) {
while (pre >= 0 && str[i] != str[pre])
pre = n[pre];
++i, ++pre;
if (i >= len)
break;
if (str[i] == str[pre])
n[i] = n[pre];
else
n[i] = pre;
}
return n;
}
public:
int strStr(string haystack, string needle) {
if (0 == needle.length())
return 0;
vector<int> n(Next(needle));
int len = haystack.length() - needle.length() + 1;
for (int i = 0; i < len; ++i) {
int j = 0, k = i;
while (j < needle.length() && k < haystack.length()) {
if (haystack[k] != needle[j]) {
if (n[j] >= 0) {
j = n[j];
continue;
} else
break;
}
++k, ++j;
}
if (j >= needle.length())
return k - j;
}
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
| func strStr(haystack string, needle string) int {
n, m := len(haystack), len(needle)
for i := 0; i <= n-m; i++ {
if haystack[i:i+m] == needle {
return i
}
}
return -1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| function strStr(haystack: string, needle: string): number {
const m = haystack.length;
const n = needle.length;
for (let i = 0; i <= m - n; i++) {
let isEqual = true;
for (let j = 0; j < n; j++) {
if (haystack[i + j] !== needle[j]) {
isEqual = false;
break;
}
}
if (isEqual) {
return i;
}
}
return -1;
}
|
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
| impl Solution {
pub fn str_str(haystack: String, needle: String) -> i32 {
let haystack = haystack.as_bytes();
let needle = needle.as_bytes();
let m = haystack.len();
let n = needle.len();
let mut next = vec![0; n];
let mut j = 0;
for i in 1..n {
while j > 0 && needle[i] != needle[j] {
j = next[j - 1];
}
if needle[i] == needle[j] {
j += 1;
}
next[i] = j;
}
j = 0;
for i in 0..m {
while j > 0 && haystack[i] != needle[j] {
j = next[j - 1];
}
if haystack[i] == needle[j] {
j += 1;
}
if j == n {
return (i - n + 1) as i32;
}
}
-1
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| /**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function (haystack, needle) {
const slen = haystack.length;
const plen = needle.length;
if (slen == plen) {
return haystack == needle ? 0 : -1;
}
for (let i = 0; i <= slen - plen; i++) {
let j;
for (j = 0; j < plen; j++) {
if (haystack[i + j] != needle[j]) {
break;
}
}
if (j == plen) return i;
}
return -1;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Solution {
public int StrStr(string haystack, string needle) {
for (var i = 0; i < haystack.Length - needle.Length + 1; ++i)
{
var j = 0;
for (; j < needle.Length; ++j)
{
if (haystack[i + j] != needle[j]) break;
}
if (j == needle.Length) return i;
}
return -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
/**
* @param String $haystack
* @param String $needle
* @return Integer
*/
function strStr($haystack, $needle) {
$strNew = str_replace($needle, '+', $haystack);
$cnt = substr_count($strNew, '+');
if ($cnt > 0) {
for ($i = 0; $i < strlen($strNew); $i++) {
if ($strNew[$i] == '+') {
return $i;
}
}
} else {
return -1;
}
}
}
|
Solution 2: Rabin-Karp String Matching Algorithm#
The Rabin-Karp algorithm essentially uses a sliding window combined with a hash function to compare the hashes of fixed-length strings, which can reduce the time complexity of comparing whether two strings are the same to $O(1)$.
Assuming the length of the string haystack is $n$ and the length of the string needle is $m$, the time complexity is $O(n+m)$, and the space complexity is $O(1)$.
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
| func strStr(haystack string, needle string) int {
n, m := len(haystack), len(needle)
sha, target, left, right, mod := 0, 0, 0, 0, 1<<31-1
multi := 1
for i := 0; i < m; i++ {
target = (target*256%mod + int(needle[i])) % mod
}
for i := 1; i < m; i++ {
multi = multi * 256 % mod
}
for ; right < n; right++ {
sha = (sha*256%mod + int(haystack[right])) % mod
if right-left+1 < m {
continue
}
// 此时 left~right 的长度已经为 needle 的长度 m 了，只需要比对 sha 值与 target 是否一致即可
// 为避免 hash 冲突，还需要确保 haystack[left:right+1] 与 needle 相同
if sha == target && haystack[left:right+1] == needle {
return left
}
// 未匹配成功，left 右移一位
sha = (sha - (int(haystack[left])*multi)%mod + mod) % mod
left++
}
return -1
}
|
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
| function strStr(haystack: string, needle: string): number {
const m = haystack.length;
const n = needle.length;
const next = new Array(n).fill(0);
let j = 0;
for (let i = 1; i < n; i++) {
while (j > 0 && needle[i] !== needle[j]) {
j = next[j - 1];
}
if (needle[i] === needle[j]) {
j++;
}
next[i] = j;
}
j = 0;
for (let i = 0; i < m; i++) {
while (j > 0 && haystack[i] !== needle[j]) {
j = next[j - 1];
}
if (haystack[i] === needle[j]) {
j++;
}
if (j === n) {
return i - n + 1;
}
}
return -1;
}
|
Solution 3: KMP String Matching Algorithm#
Assuming the length of the string haystack is $n$ and the length of the string needle is $m$, the time complexity is $O(n+m)$, and the space complexity is $O(m)$.
