LeetCode: 28. Implement strStr() (Solution with images)

Link: → https://leetcode.com/problems/implement-strstr/

Problem: →

Implement strStr().

Given two strings needle and haystack, 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().

Example 1:

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

Example 2:

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

Constraints:

• 1 <= haystack.length, needle.length <= 104
• haystack and needle consist of only lowercase English characters.

Solution: →

Here, we have given two strings one is haystack and another one is needle.

As per the given instruction we will first check if needle is not empty, if needle is empty then we will return -1. We are checking empty string by taking it’s length, if length is 0 it means it is empty string.

Same as needle we need to get length of haystack.

The reason for taking length of haystack is to check if needle string is bigger then haystack, it means whole needle will not be found in haystack, as needle have more character then haystack, if it is then we can simply return -1,

Now, we have for loop, that loop will help us to check if needle is inside haystack, if it is then return it’s index.

In for loop we will put condition like,

Here I will start with zero and go till haystackLength -needleLength + 1, the reason we have taken is because we are checking whole needle String in haystack. Like below image,

So, just i = 3, we are reaching an end of haystack String.

Now, our for loop starts with zero, and with if condition we are checking if, needle value match with first two character of haystack?

The answer is NO. So, IF condition will become false.

Now, I will become 1, and again we are checking, if needle value is matching with 2nd and 3rd character of haystack?

The answer is NO. So, IF condition will become false.

Now, I will become 2, and again we are checking, if needle value is matching with 3rd and 4th character of haystack?

The answer is YES. So, IF condition will become true.

With matching we are returning, i, this will be our first matching index.

Here i will be 2.

Code (Java): →

Code (Python) : →

Time Complexity

We are scanning the array once, hence the time complexity will be O(n).

Space Complexity

Since we have no used any extra array, the space complexity will be O(1).

Thanks for reading this article ❤

If I got something wrong? Let me in the comments. I would love to improve.

Clap 👏 If this article helps you.