Beats 100.00% of users with C++ on time.
Beats 77.68% of users with C++ on space.
Approach
This was a fun one.
The objective is to see if needle exists in haystack. If it does, return the starting index of the first occurrence of it. If it does not, return -1.
For this, I will use two pointers. One will be the iterate over haystack since this is the search area and I will use i for this.
Living outside the loop is j and this is pointer to the current position of needle.
Inside the haystack character loop, I check to see if the character at the current position in needle is equal to the character at the current position of haystack. If so, then each pointer is incremented one. If they are not equal, move i back j positions to backtrack. This is the part that is likely confusing but is responsible for situations like so:
Haystack: mississippi Needle: issip
If I didn't backtrack then the algorithm would do the following. Note this is what i = i - j prevents happening:
// i = 1, j = 0 // haystack[1] == needle[0] i == i ✅ // i = 2, j = 1 // haystack[2] == needle[1] s == s ✅ // i = 3, j = 2 // haystack[3] == needle[2] s == s ✅ // i = 4, j = 3 // haystack[4] == needle[3] i == i ✅ // i = 5, j = 4 // haystack[5] == needle[4] s != p ❌ // i = 6, j = 0 // haystack[6] == needle[0] s != i ❌
So, by backtracking, I reset the haystack iterator i back to the position after the last where the match began.
Lastly, I check to see if j == needle.length(), and if so return the starting position of the occurrence.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Code
class Solution {
public:
int strStr(string haystack, string needle) {
int j = 0;
for(int i = 0; i < haystack.length(); i++){
if(haystack[i] == needle[j]){
j++;
} else {
i = i - j;
j = 0;
}
if(j == needle.length()) return i - j + 1;
}
return -1;
}
};