Implement strStr() Solution in Python

Problem Description

Ah, the classic “find the needle in the haystack” problem! Except in this case, the needle is a string, and the haystack is also a string. The task is simple: given two strings, haystack and needle, you need to find the first occurrence of needle in haystack. If you find it, return the index of the first character of needle in haystack. If not, return -1.

Code Solution

Copy Code

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        m = len(haystack)
        n = len(needle)

        for i in range(m - n + 1):
            if haystack[i:i + n] == needle:
                return i

        return -1

Approach Explanation

The approach is straightforward: we loop through the haystack string and check if the substring starting at each index matches the needle. If we find a match, we return the index. If we finish the loop without finding it, we return -1.

Time and Space Complexity

Time Complexity: O((m – n + 1) * n) in the worst case, where m is the length of haystack and n is the length of needle.

Space Complexity: O(1) since we are using a constant amount of space regardless of the input size.

Real-World Example

Imagine you’re at a party, and you’re trying to find your friend named “John” in a crowd of people. You scan each face until you spot him. If you find him, you wave and say hi (return the index). If you don’t, you just shrug and move on (return -1).