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.