You are given two strings, haystack and needle. Return the index where needle first appears inside haystack. If needle never appears, return -1.
- 1 <= haystack.length, needle.length <= 10^4
- Both strings contain only lowercase English letters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every start position and compares character by character, which costs O(n * m) in the worst case, for example haystack = "aaaa...ab" and needle = "aaab". The waste is that after a partial match we throw away what we learned. KMP precomputes, for each prefix of needle, the length of the longest proper prefix that is also a suffix (the lps array). When a mismatch happens after matching j characters, we already know the last lps[j-1] characters match the start of needle, so we continue from there. The pointer into haystack never moves backwards, giving O(n + m).
Algorithm
- Build
lpsforneedle:lps[i]is the length of the longest proper prefix ofneedle[0..i]that is also its suffix. - Walk through
haystackwith indexiand keepj= number ofneedlecharacters matched so far. - While
j > 0andhaystack[i] != needle[j], setj = lps[j - 1]. - If the characters match, increase
j. Ifj == needle.length, returni - j + 1. - If the loop finishes, return
-1.
O(n + m)Space: O(m) for the lps arrayindexOf / find alone usually does not count as an answer.class Solution: def strStr(self, haystack: str, needle: str) -> int: m = len(needle) # lps[i] = longest proper prefix of needle[:i+1] that is also a suffix lps = [0] * m length = 0 for i in range(1, m): while length > 0 and needle[i] != needle[length]: length = lps[length - 1] if needle[i] == needle[length]: length += 1 lps[i] = lengthΒ j = 0 # characters of needle matched so far for i, ch in enumerate(haystack): while j > 0 and ch != needle[j]: j = lps[j - 1] if ch == needle[j]: j += 1 if j == m: return i - m + 1 return -1