#28
Find the Index of the First Occurrence in a String
Easy KMP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the index where needle first appears in haystack, or -1 if it doesn't appear.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: where does needle first appear in haystack?
Why this works: KMP's LPS table remembers how much of the needle still matches after a mismatch, so the haystack pointer never goes back.
Example: needle "abab" → lps [0, 0, 1, 2]
text "abaabab": match "aba", mismatch at 'a' vs 'b'jump j to lps[2] = 1 (keep "a") instead of restartingcontinue → match found at index 3
✦Hints open one at a time
The brute force tries every start: O(n·m). Fine here, but learn KMP on it.
KMP's LPS array: lps[i] = length of the longest proper prefix of needle[0..i] that is also a suffix.
On a mismatch, jump j back to lps[j - 1] instead of restarting.
↗Approach
Build the LPS table for the needle, then scan the haystack once. The haystack index never moves backwards, so the scan is linear.
</>Solution (Java)
class Solution {
public int strStr(String haystack, String needle) {
int m = needle.length();
int[] lps = new int[m];
for (int i = 1, len = 0; i < m; ) {
if (needle.charAt(i) == needle.charAt(len)) lps[i++] = ++len;
else if (len > 0) len = lps[len - 1]; // fall back, don't advance i
else lps[i++] = 0;
}
for (int i = 0, j = 0; i < haystack.length(); ) {
if (haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
if (j == m) return i - m;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
}!Common mistake
Resetting j to 0 on every mismatch — that's the brute force, and it misses overlapping matches like "aab" in "aaab".
Complexity
- Time: O(n + m).
- Space: O(m).
Topic: String Pattern Matching
🎬 Episodes 18–19: video coming soon