leetExpert
Practice

Find the Index (strStr)

Module 5 · Strings

Problem

You are given two strings: haystack (the text) and needle (the pattern). Return the starting index of the first place where needle appears inside haystack. If it never appears, return -1.

Empty needle is a match at index 0 — every string contains the empty string at its start. This is the same contract as Python's str.find and JavaScript's String.prototype.indexOf; here you implement it.

Examples

Example 1

Inputhaystack = "sadbutsad", needle = "sad"Output0

Explanation. needle begins at index 0; a later copy at 6 is ignored

Example 2

Inputhaystack = "leetcode", needle = "leeto"Output-1

Explanation. no alignment matches

Example 3

Inputhaystack = "mississippi", needle = "issip"Output4

Explanation. slice haystack[4:9] equals "issip"

Trace the third on paper — index labeling is the skill this lesson builds:

m₀ i₁ s₂ s₃ i₄ s₅ s₆ i₇ p₈ p₉ i₁₀ → at index 4 the five characters are i s s i p.

Constraints

1 ≤ lengths ≤ 10⁴ · lowercase English letters only

Attempt it first

Write the naive version cleanly — every alignment, checked honestly. Then find the worst case that makes it slow, because knowing when naive fails is this lesson's actual content.