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;
}