CODEWITHSUNDEEP
javascriptarraysalgorithmvalidation
Skeec
Skeec

Reputation: 125

Fastest way to check if string contains all substrings

Given is an array with substrings and a string that I'm checking against if it contains all of them.

Do I have to iterate over the elements and check with indexOf >= 0 or do you have any cooler ideas? Because I have to do this task over and over again any performance benefits would help thanks in advance programming language is javascript

Upvotes: 2

Views: 2757

Answers (3)

MBo
MBo

Reputation: 80285

You need an algorithm that search a finite set of patterns in one text.

The most known one with numerous implementations is Aho–Corasick algorithm.

Upvotes: 0

Bergi
Bergi

Reputation: 665040

You're looking for a cool idea and really have a lot of these substrings to test for?

It then will be a good idea performance-wise to build a suffix tree for your string, which has a lookup complexity only depending on the substring size.

You'll get down the complexity from O(len(string) * len(substring) * N_substrings)1 of the naive solution (like @BaneBojanić's one) to O(len(string) + len(substring) * N_substrings).

1: Assuming len(string) * len(substring) complexity for indexOf, it might be better than that though

Upvotes: 1

Bane Bojanić
Bane Bojanić

Reputation: 712

You can use Array.prototype.every(callback[, thisArg]); read more about it here: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/every

Basically, for your example it would be:

arr.every(function(element){
    return yourstring.indexOf(element) != -1;
});

The return value is either true or false, of course.

Upvotes: 2

Related Questions