LeetCode 28: Find the Index of the First Occurrence in a String ·

Table of Contents

Meta Data
#

Difficulty: easy First Attempt: 2022-05-11

Submissions: Accepted ×3 → Runtime Error → Accepted ×2

Approach
#

Try haystack[i:i + m] == needle at every start i (String Template 2), with starts up to n - m. In an interview present this O(nm) approach first and mention KMP’s O(n + m) if needed. Python’s str.find returns -1 when not found, exactly as required; str.index raises ValueError.

My Attempts
#

Earlier submissions used the built-in in plus index. One in 2022-10 called only haystack.index(needle), which raises ValueError when not found.

Solution
#

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

Complexity
#

Time O(nm), space O(m) (slicing).

Mistakes to Avoid
#

There are n - m + 1 starting positions.
With built-ins, index raises when not found; use find.

Interview Explanation
#

I try needle at every possible start and return the first match, or -1, in O(nm); for better bounds KMP precomputes needle’s failure function for O(n + m).