2

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.

Improve this question
3
  • 1
    you can take a look at the implementation of indexOf() here (under the caption polyfill). Commented Jan 15, 2019 at 22:27
  • 1
    Also, if you're learning and are interested in algorithmic complexity, you might want to take a look into the KMP algorithm. Commented Jan 15, 2019 at 22:32
  • 1
    Using recursion would work but would needlessly limit your comparison function to strings that fit into the call stack. You'd also incur a lot of overhead. Commented Jan 15, 2019 at 22:41

6 Answers 6

Reset to default
3

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. :-)

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

By start are you referring to the start index where that first character of the substring is found within the index?
@nrvaller yes. I try to update the text to make it more clear.
2

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"));

Improve this answer

1 Comment

You don't need the if(sub.length > str.length) return false;; the outer for-loop will never enter its body unless 0 < str.length - sub.length + 1. Also, instead of if(str[i] !== sub[0]) continue;, the inner for-loop can start at j = 0. Lastly, you may be interested in developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…, which might make this easier to read than your exists variable.
2

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'));

Improve this answer

Comments

1

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);

}
Improve this answer

Comments

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

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

Improve this answer

Comments

0

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"));

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.