We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Index of the First Occurrence in a String

Difficulty: Easy

Problem Description

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.

Key Insights

  • The problem requires finding the first index where a substring (needle) appears in a string (haystack).
  • A brute-force solution would involve checking each possible starting position in haystack for a match with needle.
  • Efficient string matching algorithms like KMP or Rabin-Karp could also be applied, but a straightforward approach is sufficient given the problem constraints.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of haystack and m is the length of needle (in the worst case). Space Complexity: O(1), no additional space is used apart from a few variables.

Solution

To solve the problem, we can use a simple loop to iterate through the haystack string, checking for matches with the needle string starting from each index. If a match is found, we return the current index. If no match is found by the end of the loop, we return -1.

Code Solutions

def strStr(haystack: str, needle: str) -> int:
    if not needle:
        return 0  # Edge case: empty needle
    n, m = len(haystack), len(needle)
    for i in range(n - m + 1):  # Loop through haystack
        if haystack[i:i + m] == needle:  # Check slice
            return i  # Return index if match found
    return -1  # Return -1 if no match found
← Back to All Questions