Find the Index of the First Occurrence in a String
The key idea
Try to anchor the needle at each possible start index of the haystack, then check character by character. The first anchor where the whole needle matches is the answer; if no anchor works, return
-1.Problem
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.
The match must be a contiguous substring: every character of needle has to line up with consecutive characters of haystack starting at the returned index. Because we want the first occurrence, scan the candidate start positions from left to right and return the earliest index where the full needle lines up.
Constraints
1 <= haystack.length, needle.length <= 10^4haystackandneedleconsist of only lowercase English characters.
Examples
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Complexity
Time: O(n * m) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization