String Search [ AKA indexOf() ] | REACTO

string-search.md

String Search (indexOf())

---

Prompt

• Given a 2 strings as input, write the function indexOf(needle, haystack) that returns the index of the first appearance of the first string (the needle) inside the second (the haystack).

• DO NOT USE built-in string methods like indexOf(), includes() or substring()

• Why can't I use these methods?

  • Whiteboard questions may aim to see if you understand the underlying concepts behind common string or array methods. You will want to show that you understand how these work under the hood.

  • Additionally, you may actually be adding more (hidden) complexity by using these methods. Look into how indexOf(), includes() and substring() work. Many built-in methods actually add another operation that's O(n), or worse.

---

Examples

indexOf('or', 'hello world'); // should return 7
indexOf('fish', 'red fish blue fish') // should return 4
indexOf('hello world', 'or'); // should return -1
indexOf('howdy', 'hello world'); // should return -1
indexOf('oox', 'ooboxoooxo'); // should return 6

---

.

.

.

.

.

Solution(s)

• Naive Approach: 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 an additional O(n) dimension in time and space, where n is the length of the haystack.

---

function indexOf (needle, haystack) {

  // only search up to diff between the length of the 2 words
  for (let hIdx = 0; hIdx <= haystack.length - needle.length; hIdx++) {
    for (let nIdx = 0; nIdx < needle.length; nIdx++) {
    
      // if no match, go back to outer for loop
      if (haystack[hIdx + nIdx] !== needle[nIdx]) break; 
      
      // if first letter of needle matches, inner for loop continues to run
      // function returns if inner for loop is able to run without breaking for the full length of needle
      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).

Why?

function indexOf (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)

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