Name: strStr()
Difficulty: Easy
Description: Find the needle in the haystack, return the first index of or -1 if not found.
Example:
Input: haystack = "hello", needle = "ll" Output: 2
Interestingly, I used simple indexing in this solution rather than iterators. I suspect, whilst very fast, the iterators were the cause of the higher memory consumption in earlier tests – remove element, for example, and merge two sorted lists etc.
int strStr(string haystack, string needle) {
int needleSize = static_cast<int>(needle.size());
int haystackSize = static_cast<int>(haystack.size());
if (needleSize > haystackSize) return -1;
if (haystackSize == needleSize) return haystack == needle ? 0 : -1;
int count = 1 + haystackSize - needleSize;
int i = 0;
while (i < count) {
int n = i;
int j = 0;
while (j < needleSize) {
if (haystack[n++] != needle[j]) {
break;
}
++j;
}
if (j == needleSize) return i;
++i;
}
return -1;
}