Check if string contains a substring in javascript

An algorithm to check if given string contains a substring.

We will implement an algorithm in javascript to search a given substring in the string. Everything will be written in ES6.

Example

Input:
'I am Prashant Yadav'
'Prashant'
'Search'
'Yadav'
'substring'
'dav'

Output:
true
false
true
false
true

Using String’s inbuilt functions to check if string contains substring

Implementation

We can use indexOf() method to check if the given string contains substring.

let hasSubString = (str, sub) => {
  return str.indexOf(sub) !== -1;
}
Input: 
console.log(hasSubString('I am Prashant Yadav', 'Prashant'));
console.log(hasSubString('I am Prashant Yadav', 'prashant'));
console.log(hasSubString('I am Prashant Yadav', 'Search'));
console.log(hasSubString('I am Prashant Yadav', 'Yadav'));
console.log(hasSubString('I am Prashant Yadav', 'substring'));
console.log(hasSubString('I am Prashant Yadav', 'dav'));

Output:
true
false
false
true
false
true

Time complexity: O(n).
Space complexity: O(1).

Time and Space complexity

  • We are checking the substring using string’s indexOf method, so Time complexity is O(n).
  • We are using constant space, so Space complexity is O(1).

Alternatively we can also use includes() method to find the substring in the given string which uses indexOf inbuilt to do the same, But it is not supported by all browsers. So you will need to use Polyfill.io or any other library.

let hasSubString = (str, sub) => {
  return str.includes(sub);
}

As you can see we can only check case sensitive substrings with this above methods.

We can solve this issue if we use Regular Expressions.

Using Regular Expressions

Implementation

  • We will use String match() method which uses regular expressions to search the substring and returns the arrays of matching objects.
let hasSubString = (str, sub) => {
  //For case sensitive
  //let re = new RegExp(sub,"g");

  //for case insensitive
  let re = new RegExp(sub,"gi");

  return (str.match(re) || []).length !== 0;
}
Input:
console.log(hasSubString('I am Prashant Yadav', 'Prashant'));
console.log(hasSubString('I am Prashant Yadav', 'prashant'));
console.log(hasSubString('I am Prashant Yadav', 'Search'));
console.log(hasSubString('I am Prashant Yadav', 'Yadav'));
console.log(hasSubString('I am Prashant Yadav', 'substring'));
console.log(hasSubString('I am Prashant Yadav', 'dav'));

Output:
true
true
false
true
false
true

Time complexity: O(1).
Space complexity: O(1).

Time and Space complexity

  • We are using regular expressions to search the substring in the string, so Time complexity is O(1).
  • We are using constant space, so Space complexity is O(1).

Regular expressions running depends upon its implementation so it can be slow some time.

Leave a Reply

Your email address will not be published. Required fields are marked *