Find the Index of the First Occurrence in a String
Find the Index of the First Occurrence in a String is LeetCode 28 (Easy). It used to be called Implement strStr(), after the C library function that does the same job.
- Given two strings
haystackandneedle, return the index whereneedlefirst appears insidehaystack. - Return
-1if it does not appear at all.
Both strings hold only lowercase letters and are at most 10⁴ characters long.
- 1 <= haystack.length, needle.length <= 10⁴
- haystack and needle consist of only lowercase English characters.
Intuition
A match can begin only at a start s where the whole needle still fits, so s runs from 0 to n - m (where n and m are the two lengths). Try each start from left to right, and compare the needle with the haystack one character at a time.
The first mismatch rules that start out, so the scan slides on to the next one. A start where all m characters agree is the answer, and because starts are tried in increasing order, it is automatically the first occurrence. If every start fails, the needle is not there.
Finding where one string first appears inside another is the base problem of string matching. This start-by-start comparison, often called naive string matching, is the baseline that faster methods such as KMP, Rabin-Karp and the Z-function improve on, so it is worth being able to write it without bugs.
Approach
Before reading on, take haystack "mississippi" and needle "issip". At which starts does the comparison get past the first character, and which start finally matches? Aim for O((n - m + 1) · m) time and O(1) extra space.
List the starts where the needle fits
A match starting at s uses positions s to s + m - 1, so s can be at most n - m. Looping over range(n - m + 1) tries exactly those starts, and the loop runs zero times when the needle is longer than the haystack.
Compare one start character by character
Set j = 0 and increase it while haystack[s + j] == needle[j]. Stop at the first mismatch: one wrong character is enough to rule out this start, so the rest of the needle does not need to be read.
Return the start on a full match
If j reached m, every needle character matched, so return s. Starts are tried left to right, so the first full match is the first occurrence, and no later start needs checking.
Return -1 only after the last start
A mismatch at one start says nothing about the next one, so the loop just moves on. Only when start n - m has also failed is it certain the needle never appears, and the function returns -1.
Find the Index of the First Occurrence in a String solution in Python | C++ | Java
s ends at s + 2. That index must be at most 8, so the last useful start is 6. Start at 0 with nothing compared yet.j reached 3, so the needle sits at index 0. Every start before it already failed, so this is the first occurrence and the scan stops. Later starts are never examined.s ends at s + 4. That index must be at most 10, so the last useful start is 6. Start at 0 with nothing compared yet.j reached 5, so the needle sits at index 4. Every start before it already failed, so this is the first occurrence and the scan stops. Later starts are never examined.s ends at s + 4. That index must be at most 7, so the last useful start is 3. Start at 0 with nothing compared yet.Common pitfalls
Trying every index of the haystack as a start
for start in range(n):
for start in range(n - m + 1):
Starts past n - m leave too few characters for the needle. With haystack "abc" and needle "cd", start 2 matches c and then reads haystack[3]: an IndexError in Python and an out-of-bounds read in C++.
Returning -1 at the first mismatch
if haystack[start + j] != needle[j]:
return -1if haystack[start + j] != needle[j]:
break # try the next startA failed start only rules out that one start. With haystack "aab" and needle "ab", start 0 fails on the second character, so this returns -1, but the needle sits at index 1.
Checking for a full match with m - 1
if j == m - 1:
return startif j == m:
return startAfter the loop, j is the number of characters that matched. With haystack "abc" and needle "abd", j stops at 2, which equals m - 1, so the wrong check reports a match at 0 even though c is not d.
Edge cases
n - m + 1 is 0 or less, so the loop never runs and the function returns -1 without reading a character.
Only start 0 fits. All characters match, so the answer is 0.
Start 2 equals n - m, which the loop includes, so the match is found and 2 is returned.
Complexity
s and j are stored.Find the Index of the First Occurrence in a String FAQ
Is this brute force fast enough, or is KMP required?
It is fast enough here. The worst input is 10,000 as with a needle of 4,999 as and a final b: about 5,000 starts times 5,000 comparisons, or 2.5 × 10⁷ steps, which runs in roughly a second even in plain Python. KMP gets O(n + m) by never moving backwards in the haystack; reach for it when an interviewer asks for linear time.
Can I just call the built-in find?
haystack.find(needle) in Python, indexOf in Java and string::find in C++ all give the same answer (C++ returns npos instead of -1). They are accepted, but interviewers ask this problem to see the loop written by hand, so mention the built-in and then write the scan.