String Search REACTO

stringSearch.md

String Search

Prompt

Create a function that attempts to find the index of the first appearance of one string inside of another. If the substring exists, returns the beginning index of the substring. Otherwise return -1. You are essentially recreating the built in string method - indexOf().

---

Examples

stringSearch('or', 'hello world'); // should return 7
stringSearch('hello world', 'or'); // should return -1
stringSearch('howdy', 'hello world'); // should return -1
stringSearch('oox', 'ooboxoooxo'); // should return 6

---

Outline && Rules

Avoid built-in methods

• Many whiteboard interviews will be language-agnostic and focus on the underlying concepts. You want to show an understanding on your problem solving skills, not that you happened to read the right documentation/problem the night before.

• Most students' first instincts will be to use built-in string methods like includes() or substring(). For this problem, steer your interviewee away from those methods. indexOf() is explicitly forbidden since you are building it.

• If your interviewee begins without asking questions, stop them and ask "Do you have any questions about the result?". Make sure that they restate the problem and ask any clarifying questions if needed. For example, one thing that might need to be clarified is if the needle/substring has to be contiguous(consecutive order) or not, which in this case, they do.

• Look into how built in methods such as indexOf(), includes() and substring() work under the hood. Many methods actually add an operation that's O(n) or worse.

---

Common approaches

split()

• Most students may look to split the haystack into an array of characters, and then loop through. This approach would work; but imagine the space complexity of generating a new array and then holding it in memory for a very, very large haystack. You would be introducing another O(n) dimension in time and space, where n is the length of the haystack.

• If that's their initial approach, have them walk through and pseudocode it; then ask them how they would do this without generating a second copy of the haystack. If they can't, let them code out their approach.

---

Solution(s)

function stringSearch(needle, haystack) {
  for (let hIdx = 0; hIdx <= haystack.length - needle.length; hIdx++) {
    for (let nIdx = 0; nIdx < needle.length; nIdx++) {
      if (haystack[hIdx + nIdx] !== needle[nIdx]) break;
      if (nIdx + 1 === needle.length) return hIdx;
    }
  }
  return -1;
}

Big O - Where n is the haystack size and m the needle size, the solution is O(n*m).

function stringSearch(needle, haystack) {
  for (let hIdx = 0; hIdx <= haystack.length - needle.length; hIdx++) {
    //O(n * ...) where n is the number of letters in haystack
    for (let nIdx = 0; nIdx < needle.length; nIdx++) {
      //O(m * ...) where m is the number of letters in needle
      if (haystack[hIdx + nIdx] !== needle[nIdx]) break;
      //O(1) constant
      if (nIdx + 1 === needle.length) return hIdx;
      //O(1) constant
    }
  }
  return -1;
  //O(1) // constant
}

So, O(n * (m * (1 + 1))) => O(n*m)

Sliding Window Approach

const stringSearch = (needle, haystack) => {
    //edge cases
    if (!needle.length || needle.length > haystack.length) return -1;

    //set up a needle pointer to track the first letter in needle
    let needlePointer = 0;

    for (let haystackPointer = 0; haystackPointer < haystack.length - needle.length; haystackPointer++) {
      let matchingIdx = haystackPointer
    
      //if they do match, use a while loop to check if the next letters match. 
      while (needle[needlePointer] === haystack[matchingIdx]) {
      //increment needlePointer and matching idx as they match
        needlePointer++
        matchingIdx++;
        //if they match AND needlePointer equals needle.length, you've found the needle. return haystackPointer
        if (needlePointer === needle.length) return haystackPointer;
      }
      //if it exits the while loop, you didnt find the needle. Reset your needlePointer pointer
      needlePointer = 0
    }
    //if you exit the for loop then there are no substrings and you can return -1.
    return -1;
};

Time Complexity - O(n*m)

There are many problems similar to this that you can practice with on LC, such as - https://leetcode.com/problems/is-subsequence/.

Video Solution Matt Mintzer There are other algorithms, such as Boyer-Moore (well, modified slightly), that can perform at O(n+m) time—or even faster.