algoadvance

Problem Statement:

You need to implement a function strStr(haystack: str, needle: str) -> int that finds the first occurrence of the substring needle in the string haystack. If needle is an empty string, return 0. If needle is not present in haystack, return -1.

Clarifying Questions:

  1. What should be returned if both haystack and needle are empty?
    • As per the problem, return 0 if needle is an empty string.
  2. Should the function consider case sensitivity?
    • Yes, typically this type of function considers case sensitivity.

Strategy:

We’ll start with a straightforward approach known as the “Sliding Window” or “Two-pointer” technique.

Steps:

  1. If needle is empty, return 0.
  2. Iterate through haystack with a window size equal to the length of needle.
  3. During iteration, check if the current window in haystack matches needle.
  4. If a match is found, return the starting index of that window.
  5. If no match is found after the iteration, return -1.

Using this approach ensures we check each possible starting position in the haystack string, verifying if needle begins there.

Time Complexity:

Now, let’s implement this in Python.

Code:

def strStr(haystack: str, needle: str) -> int:
    # If needle is an empty string
    if not needle:
        return 0
    
    # Lengths of haystack and needle
    n = len(haystack)
    m = len(needle)
    
    # Loop through haystack with a window of size m
    for i in range(n - m + 1):
        # Check if the substring of length m starting at i matches needle
        if haystack[i:i + m] == needle:
            return i
    
    # If no match is found, return -1
    return -1

Explanation:

  1. Edge Case Handling:
    • If needle is empty, return 0 immediately.
  2. Iteration:
    • The loop for i in range(n - m + 1) ensures we don’t go out of bounds while checking substrings of length m in haystack.
  3. SubString Check:
    • We use slicing haystack[i:i + m] to extract the current window and compare it directly with needle.
  4. Return the Index:
    • If a match is found, return the starting index i.
    • If the loop completes without finding a match, return -1.

This solution is straightforward and adheres closely to the problem’s requirements. Let me know if you need any further explanations or optimizations!

Try our interview co-pilot at AlgoAdvance.com