28. Find the Index of the First Occurrence in a String
1. 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.
2. Example
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.
3. Constraints
- 1 <= haystack.length, needle.length <= 10$^{4}$
- haystack and needle consist of only lowercase English characters.
4. Solutions
Two Pointers
m = haystack.size(), n = needle.size()
Time complexity: O(mn)
Space complexity: O(1)
class Solution {
public:
int strStr(const string &haystack, const string &needle) {
const int m = haystack.size(), n = needle.size();
for (int i = 0; i <= m - n; ++i) {
int j = 0;
while (j < n && haystack[i + j] == needle[j]) {
++j;
}
if (j == n) {
return i;
}
}
return -1;
}
};
KMP
m = haystack.size(), n = needle.size()
Time complexity: O(m + n)
Space complexity: O(n)
class Solution {
public:
int strStr(const string &haystack, const string &needle) {
const int m = haystack.size(), n = needle.size();
vector<int> next(n, 0);
int length = 0;
for (int i = 1; i < n; ++i) {
while (length > 0 && needle[i] != needle[length]) {
length = next[length - 1];
}
if (needle[i] == needle[length]) {
++length;
}
next[i] = length;
}
int matched = 0;
for (int i = 0; i < m; ++i) {
while (matched > 0 && haystack[i] != needle[matched]) {
matched = next[matched - 1];
}
if (haystack[i] == needle[matched]) {
++matched;
}
if (matched == n) {
return i - n + 1;
}
}
return -1;
}
};