LeetCode - The World's Leading Online Programming Learning Platform

Intuition

Scan haystack by needle.

Approach

Set left and right pointers, scan from left to right, and check if the substring of haystack within the interval is equal to needle.

Complexity

• Time complexity: O(n×m)
• Space complexity: O(1)

Code

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == haystack:
            return 0

        l = 0
        r = len(needle)

        while r <= len(haystack):
            if haystack[l:r] == needle:
                return l
            l += 1
            r += 1

        return -1