Return the index of the first occurrence of needle in haystack, or
needle is not part of
What should we return when
needle is an empty string? This is a great question to ask during an interview.
Input: haystack = "hello", needle = "ll" Output: 2
Input: haystack = "aaaaa", needle = "bba" Output: -1
Input: haystack = "", needle = "" Output: 0
0 <= haystack.length, needle.length <= 5 * 104
needleconsist of only lower-case English characters.
We can solve this question using both the Naive Approaches as well as using KMP Algorithm.
Naive Approach: Traverse all the possible starting points of
haystack.length() - needle.length()) and see if the following characters in
haystack match those of
Time Complexity: O(mn)
Space Complexity: O(1)
KMP Algorithm: Finally comes the KMP algorithm. You may refer to KMP on jBoxer's blog for some explanations.
Time Complexity: O(m+n)
Space Complexity: O(n)