28. Implement strStr()
Model: qwen2.5-coder:14b
Topics: Two Pointers,String
FAANG asked: 1
Acceptance rate: 35.3%
Problem Breakdown
The problem requires implementing a function strStr() that returns the index of the first occurrence of the substring needle in the string haystack. If needle is not found within haystack, the function should return -1. An important edge case to consider is when needle is an empty string, for which the function should return 0.
Inputs:
haystack: A string where we are searching for a substring.needle: The substring we are looking for withinhaystack.
Outputs:
- An integer representing the index of the first occurrence of
needleinhaystack, or-1ifneedleis not found.
Implicit Constraints/Edge Cases:
- If
needleis an empty string, return0. - If
haystackis shorter thanneedle, return-1. - If
haystackandneedleare both empty strings, return0.
Intuition
A brute-force approach would involve checking every possible starting position in haystack to see if the substring matches needle. This approach has a time complexity of O(n * m), where n is the length of haystack and m is the length of needle, which can be inefficient for large inputs.
The key insight to improve this is to use the Knuth-Morris-Pratt (KMP) algorithm, which preprocesses needle to create a partial match table. This allows us to skip unnecessary comparisons when a mismatch occurs, reducing the time complexity to O(n + m).
Approach
-
Preprocess
needleusing KMP Algorithm:- Create an array
lps(Longest Prefix Suffix) wherelps[i]is the length of the longest proper prefix which is also a suffix for the substringneedle[0...i]. - This preprocessing step takes O(m) time.
- Create an array
-
Search for
needleinhaystack:- Use two pointers, one for
haystackand one forneedle. - Compare characters of
haystackandneedle. - If a mismatch occurs and the current character of
needleis not part of a prefix which is also a suffix, move the pointer inhaystackforward. - If a match is found, move both pointers forward.
- If the end of
needleis reached, return the starting index of the match inhaystack. - If the end of
haystackis reached without finding a match, return-1.
- Use two pointers, one for
Complexity Analysis
- Time Complexity: O(n + m), where n is the length of
haystackand m is the length ofneedle. This is due to the linear time complexity of both the preprocessing step and the search step. - Space Complexity: O(m) for storing the
lpsarray.
Solution
def strStr(haystack: str, needle: str) -> int:
if not needle:
return 0
def compute_lps(pattern):
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
lps = compute_lps(needle)
i, j = 0, 0
while i < len(haystack):
if haystack[i] == needle[j]:
i += 1
j += 1
if j == len(needle):
return i - j
elif i < len(haystack) and haystack[i] != needle[j]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return -1
Edge Cases Handled
- Empty
needle: The function returns0immediately. haystackshorter thanneedle: The loop will not find a match, and the function will return-1.- Both
haystackandneedleare empty strings: The function returns0.