Find the Index of the First Occurrence in a String easy

Problem Statement

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

Example 1:

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

Example 2:

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

Steps:

1. Handle Base Cases: If needle is an empty string, return 0 (an empty string is considered to be present at the beginning of any string). If needle is longer than haystack, return -1 (it cannot be found).

2. Iterate Through haystack: Use a loop to iterate through haystack until the remaining portion is shorter than needle.

3. Compare Substrings: In each iteration, compare the current substring of haystack (of the same length as needle) with needle.

4. Return Index: If a match is found, return the starting index of the match in haystack.

5. Return -1: If the loop completes without finding a match, return -1.

Explanation:

The solution employs a straightforward string matching approach. It iterates through the haystack string, comparing substrings of the same length as the needle string. The substring() method efficiently extracts the substrings for comparison. The loop continues until either a match is found or the remaining portion of haystack is too short to contain needle. This avoids unnecessary comparisons.

Code:

function strStr(haystack: string, needle: string): number {
    // Handle base cases
    if (needle === "") {
        return 0;
    }
    if (needle.length > haystack.length) {
        return -1;
    }

    // Iterate through haystack
    for (let i = 0; i <= haystack.length - needle.length; i++) {
        // Compare substrings
        if (haystack.substring(i, i + needle.length) === needle) {
            return i; // Return index if match is found
        }
    }

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

Complexity:

• Time Complexity: O(m*n), where 'm' is the length of haystack and 'n' is the length of needle. In the worst case, we might compare all possible substrings of haystack. However, on average, it's much faster. More efficient algorithms like Knuth-Morris-Pratt (KMP) exist for better performance in worst-case scenarios.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input size. We are not creating any data structures that scale with input size.