LeetCode | Implement strStr() | Google Interview Questions | Geek Hacker

Problem Statement

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Constraints

• 0 <= haystack.length, needle.length <= 5 * 104
• haystack and needle consist of only lower-case English characters.

Examples

Example 1

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Example 3

Input: haystack = "", needle = ""
Output: 0

Analysis

In order to design a function that is similar to the strstr() in C, we will use a sliding window of the same size as needle to scan the substrings of haystack.

Algorithm

1. Calculate the length of the needle as needleLength.
2. Scan the haystack from left to right and slide the window of size needleLength.
3. Check if substrings of length needleLength are present or not.

Python 3 Code

def strStr(self, haystack, needle):
   # Base conditions
   if haystack is None or needle is None:
      return -1
   # Special case
   if haystack == needle:
      return 0
   # Length of the needle
   needleLength = len(needle)
        
   # Loop through the haystack and slide the window
   for i in range(len(haystack) - needleLength + 1):
      if haystack[i:i + needleLength] == needle:
         return i
            
   return -1

Complexity

Time Complexity

O(n) because the string is traversed once.

Space Complexity

O(n) because in the worst case scenario, we may have to create n substrings of length 1 each.

For more LeetCode problems’ solutions, visit my GitHub repo.

If you enjoyed reading this article, please recommend and share it to help others find it!