CODEWITHSUNDEEP
javascriptalgorithm
nrvaller
nrvaller

Reputation: 373

Find substring in string without includes/indexOf/Regex in Javascript

I'd like to figure out if a substring is within a string without using the Javascript built in methods of includes, indexOf, (any similar to those), or regular expressions. Basically just looking to learn an algorithm approach.

This is what I have so far

function isSubstring(string, substring){
    substringIndex = 0;

    // loop through string
    for(let i = 0; i< string.length; i++){

       //check the current substring index if it matches 
       if(string[i] === substring[substringIndex]){
           substringIndex++
          //continue searching... Would i then have to call another function recursively?
       }

    }

}

I'm having trouble understanding how to build the algorithm. Once it finds that first character that matches, I would just go to the next one and if it matches continue to the next index of the string? Would I then need a recursive function that is separate from the looping I am currently doing? I'm trying to get better at algorithmic thinking. Thanks.

Upvotes: 2

Views: 4744

Answers (6)

Niket Tongare
Niket Tongare

Reputation: 632

using only one loop pseudo code :

const containSubstr = (str, substr) => {
  let count = 0;
  let i = 0;
  let startIndex = 0;

  while (i < str.length) {
    if (substr[count] === str[i]) {
      if (count === substr.length - 1) {
        return true;
      }
      count++;
    } else {
      count = 0;
      i = startIndex;
      startIndex++;
    }
    i++;
  }
  return false;
};

console.log(containSubstr("ababad", "abad"));

Upvotes: 0

Rick Edwards
Rick Edwards

Reputation: 67

    function isSubstring(str, sub) {
        return str.split(sub).length > 1
    }

No includes, no .indexOf, no RegExp. Just strings.

Upvotes: 0

Al Kepp
Al Kepp

Reputation: 5980

Many approaches are possible. Here is one: Create a simpler function which will check if a first string is at concrete specified position, let's call it start, in a second string. It is quite simple: You compare first[i] with second[start+i] for all i in range 0 to length of first - 1.

Then the second step will be to repeat this function for all start positions from 0 to length of second string, while checking the boundaries (you cannot read after end of a string).

You can also do some optimizations later, when the first version will work. :-)

Upvotes: 3

גלעד ברקן
גלעד ברקן

Reputation: 23955

Since you expressed interest in a recursive method, here's something to consider. Clicking on the yellow markdown parts reveal the spoilers.

function f(str, sub, i=0, j=0){
  if (j && j == sub.length)

return true;

  if (i == str.length)

return false;

  if (str[i] == sub[j])
    return f(str, sub,

i+1, j+1);

  return f(str, sub,

i+1, 0);

}

Upvotes: 1

kockburn
kockburn

Reputation: 17636

Here is an optimized example of the algorythm isSubstring. It iterates only through the minimum number of characters required.

For example, if the string is 20 characters long and the substring is only 5 characters long, when we get to the 16th position of the string we can assume that the substring doesn't exist within the string (16 + 5 = 21 > 20)

function isSubstring(str, sub){
  if(sub.length > str.length) return false;
  for(let i = 0; i < str.length - sub.length + 1; i++){
    if(str[i] !== sub[0]) continue;
    let exists = true;
    for(let j = 1; j < sub.length && exists; j++){
        if(str[i+j] === sub[j]) continue;
        exists = false;
    }
    if(exists) return true;
  }
  return false;
}

//expected true
console.log(isSubstring("hello world", "hello"));
console.log(isSubstring("hello world", "world"));
console.log(isSubstring("hello world", "d"));
console.log(isSubstring("hello world", "o w"));
console.log(isSubstring("hello world", "rl"));
console.log(isSubstring("hello world", ""));

//expected false
console.log(isSubstring("hello world", "hello world 1"));
console.log(isSubstring("hello world", "helloo"));

Upvotes: 2

CertainPerformance
CertainPerformance

Reputation: 371203

On each iteration over the length of the haystack, use slice to extract the characters from that index to (the index plus the length of the needle). If the sliced string matches the needle, return true:

function isSubstring(string, substring) {
  for (let i = 0; i < string.length; i++) {
    const sliced = string.slice(i, i + substring.length);
    if (sliced === substring) {
      return true;
    }
  }
  return false;
}
console.log(isSubstring('foobar', 'oob'));
console.log(isSubstring('foobar', 'baz'));

Upvotes: 2

Related Questions