illuminati

1 min

Implement StrStr Interviewbit Solution

Updated: Dec 13, 2020

Problem: Implement StrStr

Problem Statement:

Implement strStr().
  strstr - locate a substring ( needle ) in a string ( haystack ).
 
 Try not to use standard library string functions for this question.
 Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

NOTE:
  Good clarification questions:

  1. What should be the return value if the needle is empty?

  2. What if both haystack and needle are empty?

For the purpose of this problem, assume that the return value should be -1 in both cases.

Approach

Approach is to use a sliding window concept. Take a prefix of string B of size equal to the size of string A. And then keep moving forward and append the new character at the end, and remove the first character from the start. For each iteration keep comparing our current string with string A. If there is a match return the index from which the our current string has started.

Time & Space Complexity

Time Complexity: O(N*M)
 Space Complexity: O(M)

Where, N and M is the size of string B & A respectively.

Solution

Code in C++