Leetcode – strStr()

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s