Find the Index of the First Occurrence in a String easy

Problem Statement

Implement strStr().

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.

Clarification:

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

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Example 1:

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

Example 2:

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

Steps

1. Handle Empty Needle: If the needle is empty, return 0 as per the problem statement.
2. Iterate through Haystack: Iterate through the haystack string using a loop.
3. Check for Needle: At each position in the haystack, compare the substring of the haystack (starting at the current position and having the same length as the needle) with the needle.
4. Match Found: If a match is found, return the current index.
5. No Match: If the loop completes without finding a match, return -1.

Explanation

The solution uses a simple string matching approach. It iterates through the haystack, checking if the needle is present at each possible starting position. The substr function is used to efficiently extract substrings for comparison. The time complexity is directly proportional to the lengths of both the haystack and the needle, while the space complexity is constant (O(1)) because we are not using any extra data structures whose size depends on the input.

Code

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.length();
        int m = needle.length();

        // Handle empty needle case
        if (m == 0) {
            return 0;
        }

        // Iterate through haystack
        for (int i = 0; i <= n - m; ++i) {
            // Check for match
            bool match = true;
            for (int j = 0; j < m; ++j) {
                if (haystack[i + j] != needle[j]) {
                    match = false;
                    break;
                }
            }

            // Return index if match found
            if (match) {
                return i;
            }
        }

        // Return -1 if no match found
        return -1;
    }
};

Complexity

• Time Complexity: O(n*m), where n is the length of haystack and m is the length of needle. In the worst case, we might compare the needle with every possible substring of the haystack.
• Space Complexity: O(1). The algorithm uses only a constant amount of extra space, regardless of the input sizes. We're not creating new data structures whose sizes depend on the inputs.