28 Implement strStr()
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
- The biggest part of the problem was identifing edge cases.
- O(N) time
- O(1) space
int strStr(string haystack, string needle) {
// are the same
if (needle == haystack) return 0;
// invalid cases
else if (haystack.length() == 0 ||
needle.length() > haystack.length()) return -1;
// nothing can be anything, so return first index
else if (needle.length() == 0) return 0;
int length_n = needle.length();
for (int i = 0; i < haystack.length() - length_n; i++) {
if (haystack.substr(i, length_n) == needle) {
return i;
}
}
// check right edge case
if (haystack.substr(haystack.length() - length_n, length_n) == needle)
return haystack.length() - length_n;
return -1;
}
Last modified 4yr ago