28. Find the Index of the First Occurrence in a String

Find the Index of the First Occurrence in a String

Problem Description

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.

 

Example 1:

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

Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1

Explanation: "leeto" did not occur in "leetcode", so we return -1.

 

Constraints:

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

Approach) Brute force

Code:

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    let len = needle.length;
    if(!needle || !len){
        return -1;
    }
    
    for(let i=0;i<haystack.length;i++){
        if(haystack.slice(i,i+len) === needle){
            return i;
        }
    }
    return -1;
};

OR

var strStr = function(haystack, needle) {
	// Make sure to cut it short if needle is bigger than haystack or null (0)
    if (needle.length === 0 || needle.length > haystack.length) return -1;
    
    let first = 0;
    let second = 0;
    
    while (first < haystack.length) {
		// We want to continue to check until the first string of each word matches
        if (haystack[first] === needle[second]) {
			// Now iterate needle to check if its all the same
            while (second < needle.length) {
				// If not not the same. break
                if (haystack[first + second] !== needle[second]) break;
				// Continue moving up the needle index
                second++;
            }
            
			// If we got to the end without breaking, just return first as it is the first index that matched
            if (second === needle.length) return first;
			// reset back to second being 0 if we haven't found it
            second = 0;
        }
        
		move up and repeat
        first++;
    }
    
    return -1;
};

Approach) JS In Built Method

Code:

var strStr = function(haystack, needle) {
    return haystack.search(needle)
};

Approach) Two Pointer

Code:

var strStr = function(haystack, needle) {
  let p1 = 0;
  let p2 = 0;
  if (needle.length == 0) {
    return 0;
  }
  while (p1 < haystack.length) {
    if (haystack[p1] == needle[p2]) {
      p2++;
    } else {
      p1 = p1 - p2;
      p2 = 0;
    }
    p1++;
    if (p2 == needle.length) { 
      return p1 - p2;
    }
  }
  return -1;
};

Approach) KMP (Knuth Morris Pratt Algorithm)

Note: I found it helpful on KMP: https://www.youtube.com/watch?v=GTJr8OvyEVQ

Code:

var strStr = function(haystack, needle) {
    if (needle.length === 0) return 0;
    const lps = kmp(needle);
    let j = 0;
    for (let i = 0; i < haystack.length;) {
        if (haystack[i] === needle[j]) {
            if (j < needle.length - 1) {
                i++;
                j++
            } else {
                return i - j;
            }
        } else if (haystack[i] !== needle[j]) {
            if (j === 0) {
                i++;
            } else {
                j = lps[j - 1];
            }
        }
    }
    return -1;
};

var kmp = function(needle) {
    const lps = new Array(needle.length).fill(0);
    let j = 0;
    for (let i = 1; i < lps.length;) {
        if (needle[i] !== needle[j]) {
            if (j === 0) {
                i++;
            } else {
                j = lps[j - 1];
            }
        } else if (needle[i] === needle[j]) {
            lps[i] = j + 1;
            j++;
            i++;
        }
    }
    return lps;
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem #28. Find the Index of the First Occurrence in a String

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!