LeetCode #28 Find the Index of the First Occurrence in a String

Javascript – LeetCode problem #28 Find the Index of the First Occurrence in a String

In this problem, we need to create a method that detects if a given string (needle) occurs in another string (haystack) and return the index. Read the problem on LeetCode.

Going letter by letter?

It’s pretty obvious that we need some form of loop to compare both strings with each other. One option would be to evaluate letter by letter. If, for example, needle was “car”, we would start by checking for “c”. If we found the first “c” in haystack, we would then check if the next letter in haystack was “a”. If so, we continue checking for the last letter. Else, we would have to start over and check for the next “c”.

That approach would be perfectly functional, however it doesn’t seem like the most effective. We need to run the comparison and check for continuation, plus handle potential resets. However, there is a way to simplify the approach by using the substring() function.

Solution – Going substring by substring

I approached this by creating a two pointer loop. I set the first pointer (p1) to 0 and the second pointer (p2) to the length of the target (needle). With this spacing, I can create a substring of haystack of the same length as needle and move the pointers until a match was found (return p1) or the loop breaks (return -1).

Example:

haystack = "gocargo"
needle = "car"  -> length 3 -> p1=0, p2=3

1) "goc" == "car" -> false
2) "oca" == "car" -> false
3) "car" == "car" => true

This is less verbose than checking letter by letter and we don’t need to worry about checking continuation of matches. Since we are only looking for the first occurrence of needle, it’s also a good idea for efficiency to break the loop once a match has been found.

Here’s the full code:

var strStr = function(haystack, needle) {
    let p1 = 0;
    let p2 = needle.length;
    let indexOut = -1;

    while(p2<=haystack.length){
        if(haystack.substring(p1,p2) == needle){
            indexOut = p1;
            break;
        }
        else{
            p1++
            p2++
        }
    }
    return indexOut;
};

That’s how I solved LeetCode problem #28 Find the Index of the First Occurrence in a String. More LeetCode solutions.