Technical Interview Question: Implement strStr()

You are given two strings, haystack and needle. Your task is to implement the strStr() function, which returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

You must not use any built-in library function such as indexOf().

Note:

• When needle is an empty string, the function should return 0.

Implement the strStr() function.

Example:

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

Note: In this example, "ll" can be found at index 2 in the string "hello".

Solution Explanation

To solve this problem, we will use a sliding window approach.

1. First, we will check if the needle is an empty string. If it is, we will return 0, as stated in the problem.

2. Next, we will loop through the haystack string using a sliding window of length equal to the needle string.

3. In each iteration, we will compare the current window with the needle string using the == operator. If they are equal, we will return the starting index of the window.

4. If the window does not match the needle string, we will slide the window one position to the right by incrementing the starting index of the window by 1.

5. If we reach the end of the haystack string without finding a matching window, we will return -1 to indicate that the needle string is not part of the haystack string.

Let's see the implementation of the solution in Python.

Python Implementation

def strStr(haystack: str, needle: str) -> int:
    if needle == "":
        return 0
    
    n, m = len(haystack), len(needle)
    for i in range(n - m + 1):
        if needle == haystack[i:i+m]:  # Check if the current window matches the needle
            return i
    
    return -1

The time complexity of this solution is O((n-m+1)m), where n is the length of haystack and m is the length of needle. In the worst case, we will have to compare all possible windows of length m with the needle string.