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

EasyLeetCode

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.

Example 1:

Input: haystack = "sadbutsad", needle = "sad" Output: 0 Explanation: "sad" occurs at index 0 and 6. The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto" Output: -1 Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

• 1 <= haystack.length, needle.length <= 10^4
• haystack and needle consist of only lowercase English characters.

How to solve the problem

• Use a sliding window approach to check each possible starting position in haystack.
• For each position, compare the substring with needle character by character.
• Return the first position where a match is found, or -1 if no match exists.

Code

• Approach 1: Character-by-Character Comparison

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        result = 0
        for i in range(len(haystack) - len(needle) + 1):
            for j in range(len(needle)):
                if haystack[i + j] != needle[j]:
                    break
            else:
                return i
        return -1

• Approach 2: String Slicing

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack) -  len(needle) + 1):
            if haystack[i:len(needle) + i] == needle:
                return i
        return - 1

Complexity

• Approach 1(Character-by-Character Comparison)

• Time complexity: O(nm): For each position in haystack (O(n)), we compare with needle character by character (O(m)), so in total is O(nm).

• Space complexity: O(1): We only use a constant amount of extra space for variables.

• Approach 2(String Slicing)

• Time complexity: O(nm): For each position in haystack (O(n)), we create a substring slice and compare with needle (O(m)), so in total is O(nm).

• Space complexity: O(m): We create a substring slice of length m for each comparison.