Coding

Leetcode Implement strStr problem solution

5
(1)

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

The problem statement looks simple. Basically we need to find if haystack string contains needle string, and if yes then return that particular index of haystack string from where needle string starts, otherwise return -1.

Most of the blogs or youtube videos where you see any kind of problem solving for these kind of problems, they will simply explain you the solution. While the solution of the problem could be helpful to you, they will not explain how their mind worked in order to come to that solution. Ultimately whether in interviews or in your real job, you will not get the same exact problem, but once your mind is trained on how you approach these problems, that will ultimately help solve unknown problems.

Coming back to this problem of strstr(), I went through the problem and then overthought it a bit. My first approach was to apply a new shiny algorithm (Rabin Karp String algorithm) to solve this. The approach would be to start from beginning from haystack string and calculate sum of all characters of first k characters of haystack string where k is length of needle string. Now match if this sum is equal to sum of all characters of needle string. If yes, then check if both these strings (first k characters of haystack string and complete needle string) are equal, then return the starting index of haystack string. If not, then move to next character, subtract first character value from sum, add last character value to sum and repeat above steps till you reach end of string.

While this approach sounds very cool to show off, first off it takes a lot of time to implement (remember either in interview or in job, people always appreciate if you first come up with working solution). I tried implementing this, was almost able to do this after spending quiet some time, but was missing a lot of corner cases.

I was feeling frustrated that I was not getting to the right solution. So I shut down my system and went for a jog. You can’t do that in an interview. 🙂

I came back the next day, removed all the code that was written and gave the problem a fresh start. This time I iterated from the beginning of haystack and compared first k characters with those in needle string (where k is length of needle string) and as soon as I found them equal, I returned that index. In the end if I could not find any equality I returned -1.

Below is the solution.

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length()>haystack.length())
          return -1;
        
        int needleLen = needle.length();
        int haystackLen = haystack.length();
        for (int i=0; i<haystack.length(); i++) {
            if (i+needleLen>haystack.length()) return -1;
            
            String sub = haystack.substring(i, i+needleLen);
            if (sub.equals(needle))
                return i;
        }
        return -1;    
                
    }    
   
}

And below is how fast and memory efficient the solution compared to all submitted leetcode solutions.

Lessons that I learnt and you can also incorporate.

  • Just because you have learnt a new shiny algorithm or a technique, don’t try directly applying the same.
  • It is almost always better to first come up with a brute force solution and then optimize it rather than overthinking the problem and keep thinking of fancy solutions without solving them.
  • When you are doing problem solving practice, sometimes it is perfectly ok to take a break, remove everything and start from scratch. Unable to solve an easy problem does not make you less of an engineer and solving a hard problem does not entitle you title of genius.

How useful was this post?

Click on a star to rate it!

Average rating 5 / 5. Vote count: 1

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?