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

String Searching - Code Explanation

In this blog post, we will explain the code for finding the first occurrence of a string within another string in C++. We will provide the code implementation, analyze its complexity, and give an example to demonstrate its usage.

Code Explanation

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

            for (int windowStart = 0; windowStart <= n - m; windowStart++)
            {
                for (int i = 0; i < m; i++)
                {
                    if (needle[i] != haystack[windowStart + i])
                        break;
                    if (i+1 == m)
                        return windowStart;
                }
            }
            return -1;
        }
    };

The given code defines a class named "Solution" that contains a function named "strStr". This function takes two string parameters, "haystack" and "needle". The goal is to find the index of the first occurrence of the "needle" string within the "haystack" string.

The code uses two variables, "m" and "n", to store the sizes of the needle and haystack strings, respectively.

The code then utilizes a nested for loop structure to iterate over all possible windowStart positions in the haystack string. The outer loop runs from 0 to (n - m), ensuring that there are enough characters in the haystack for the needle to fit.

Inside the outer loop, the inner loop iterates over each character of the needle string. It compares the characters of the needle and haystack at corresponding positions (windowStart + i) to check for a match. If the characters do not match, the inner loop breaks, and the next windowStart position is examined.

If the inner loop completes without any breaks, it means that the entire needle string has been matched successfully in the current window. In this case, the code returns the current windowStart position as the index of the first occurrence of the needle in the haystack.

If no match is found after examining all possible windowStart positions, the code returns -1 to indicate that the needle is not part of the haystack.

Complexity Analysis

The time complexity of this code is O((n - m) * m), where n is the length of the haystack string and m is the length of the needle string. This is because the code iterates over (n - m) windowStart positions, and for each position, it compares at most m characters of the needle with the corresponding characters of the haystack.

The space complexity of the code is O(1) since it uses a constant amount of additional space for storing variables, regardless of the input sizes.