28. Find the Index of the First Occurrence in a String

The Problem

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Examples

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

• 1 <= haystack.length, needle.length <= 104
• haystack and needle consist of only lowercase English characters.

The solution

We opted for a simple approach using a for loop, this was the result:

int strStr(string haystack, string needle) {
	int limit = haystack.size() - needle.size() + 1;
    if(limit < 0) return -1;
    int equal = 0, pos = -1;

        for(int i = 0; i < limit; ++i){
			equal = 0;
			for(int j = 0; j < needle.size(); ++j){
				if(haystack[i + j] != needle[j]) break;
				else ++equal;
			}
            
		if(equal == needle.size()) {
			pos = i;
			break;
		}
	}

	return pos;
}

Let's break down this code step by step:

1. int limit = haystack.size() - needle.size() + 1: Here, we calculate the difference in size between the haystack and the needle to ensure our loop doesn't go out of bounds.
2. if(limit < 0) return -1: This line checks if the needle is longer than the haystack. If so, we return -1 to indicate that the needle was not found.
3. int equal = 0, pos = -1: We initialize two variables: equal, which will count the number of elements found, and pos, which will store the answer to this problem.
4. for(int i = 0; i < limit; ++i): We create a loop from 0 to the calculated limit.
5. equal = 0: We reset the count of found elements to 0 for each index.
6. for(int j = 0; j < needle.size(); ++j): This loop iterates over the characters of the needle to check if they are found in the haystack.
7. if(haystack[i + j] != needle[j]) break: Here, we compare characters between the haystack and the needle. If they are different, we break out of the loop.
8. else ++equal: If the characters match, we increment the count of found elements by 1.
9. if(equal == needle.size()): If the count of found elements equals the size of the needle, it means we found the word in the haystack at the current index i. So, we set our answer pos to the value of i and break out of the loop.
10. return pos: Finally, we return the answer stored in pos.