Implement strStr()

Description#

Implement the strStr() function.

Given a haystack string and a needle string, find the first occurrence of the needle string in the haystack string (starting from index 0). If it doesn't exist, return -1.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Note:

What should we return when needle is an empty string? This is a good question to ask during an interview.

For this problem, we will return 0 when needle is an empty string. This is consistent with the definition of strstr() in C and indexOf() in Java.

Approach#

Return 0 if needle is an empty string.
Traverse the haystack string and check if the current character matches the first character of needle. If not, continue traversing.
If the characters match, check if the remaining characters match as well. If needle is fully traversed, return the matching position. If haystack is fully traversed, return -1. If a mismatch is found, break out of the loop and continue matching the first character.
If the haystack traversal is completed without a full match, return -1.

int strStr(char * haystack, char * needle) {
    if(strlen(needle) == 0)
        return 0;
    for(int i=0;haystack[i] != '\0';i++) {//traverse the string
        if(needle[0] == haystack[i]) {//check for first character match
            for(int j=0;;j++) {//match the remaining characters
                if(needle[j] == '\0')
                    return i; 
                if(haystack[i+j] == '\0')
                    return -1;
                if(needle[j] != haystack[i+j]) //mismatch in remaining characters
                    break;//break out of current match  
            }
            continue;//check for next first character
        }
    }
    return -1;//no match for first character
}

Note#

The order of checking the return conditions during matching is strictly required. Return success when needle is fully matched, return -1 when needle is not fully matched but haystack traversal is completed, and only then check for a match.