Find if a String contains a match from a list of words Efficiently?

user_7805613 0
Viewed 637

I have a set of words like

var words = ["champ", "winner", "world"];

var string = "I am a champ"; should match 
var string2 = "I am achamp";  should match
var string3 = "I am a win ner";  should match winner [or for efficency we can prevent match too, but only last resort]
var string4 = "I am not able to figure this"; no 


// I want to be able to match the words in string, string1, string2 with the words in the  // list of array efficently as the word array will be huge in size.This is what i have //  // conjured. 


var x = string.split(' ');
var x1 = string2.split(' ');
var x2 = string3.split(' ');
var x3 = string4.split(' ');

if (words.some(v => x1.includes(v))) { // only works for string but not for others
    console.log('Yes');
} else {
  console.log('No');
}

How to make sure i am able to match words in my sentence efficiently and also we can have punctuation like " ? / etc , which i am thinking to remove and work with to make the check easier . how can i do it efficiently and fast in client as the list can be atleast 1k.

javascript
7 Answers

This approach allows any character to come in between the characters of the search strings

let words = ["champ", "winner", "world"];
let strings = [
    "I am a champ",
    "I am achamp",
    "I am a win ner",
    "I am not able to figure this",
    "w_o_r_l_d"
];
let regexes = [];

for (let element of words) {
    regexes.push(element.split('').join('.*?'));
}

let regex = new RegExp(regexes.join('|'));

for (const string of strings) {
    if (string.match(regex)) {
        console.log('Yes');
    } else {
        console.log('No');
    }
}

OUTPUT: Yes Yes Yes No Yes

This approach only allows spaces to come in between the characters of the search strings

let words = ["champ", "winner", "world"];
let strings = [
    "I am a champ",
    "I am achamp",
    "I am a win ner",
    "I am not able to figure this",
    "w_o_r_l_d"
];
let regex = new RegExp(words.join('|'));

for (let i in strings) {
    strings[i] = strings[i].replace(/\s/g, '');
}

for (const string of strings) {
    if (string.match(regex)) {
        console.log('Yes');
    } else {
        console.log('No');
    }
}

OUTPUT: Yes Yes Yes No No

user_138933350

You can do a simple regex for a sentence. As for permutations, you should decide on a strategy, otherwise, you might face an infinite number of options.
for example, does space between letters count, and if so, does two words without space count as well, and so on.

Anyway, the following code should do the trick for the first two sentences:

/**
 * 
 * @param {String[]} words
 * @param {string} sentence
 * @returns {boolean}
 */
const match = (words, sentence) => {
      return !!words.some(word => {
          const regex = new RegExp(word, "i"); // the "i" is for case-insensitive, in case you wish to have it case-sensitive, remove the "i"
          return regex.test(sentence)
      });
    };
    
    
    
const words = ["champ", "winner", "world"];
const string = "I am a champ"; //should matchmatch(words, string)

const string2 = "I am achamp";  //should match
const string3 = "I am a win ner"; // should match winner [or for efficency we can prevent match too, but only last resort]
const  string4 = "I am not able to figure this"; //no

console.log(match(words, string)) // true
console.log(match(words, string2))// true
console.log(match(words, string3))// false - unless you wish to have all the permutations of the original string
console.log(match(words, string4)) //false

user_16276400 
words.some(function(v) { return string.indexOf(v) >= 0; })


var words = ["champ", "winner", "world"];

var string = "I am a champ";
var string2 = "I am achamp";
var string3 = "I am a win ner";
var string4 = "I am not able to figure this";


// I want to be able to match the words in string, string1, string2 with the words in the  // list of array efficently as the word array will be huge in size.This is what i have //  // conjured. 


var x = string.split(' ');
var x1 = string2.split(' ');
var x2 = string3.split(' ');
var x3 = string4.split(' ');

if (words.some(function(v) { return string.indexOf(v) >= 0; })) { // only works for string but not for others
    console.log('Yes');
} else {
  console.log("no");
}

user_86042160

One possible approach could be create a Map from the Words list so the complexity of checking if the word at string is also at your word list is O(1). This would be transformed into code by this way:

let map = new Map<string,boolean>();
words.forEach(w => map.set(w,true))
string1.split(' ').some(w => map.has(w))
user_123222770

You could use this library. To be able to find "win ner" remove all whitespaces before searching with AhoCorasick algorithm.

var ac = new AhoCorasick(["champ", "winner", "world"]);
var mystring = 'I am a win ner.';
var results = ac.search(mystring.replace(/ /g,''));

console.log(results.length > 0);
<script src="https://cdn.jsdelivr.net/gh/BrunoRB/ahocorasick/src/main.js"></script>

user_68719290

RegExp's are the answer, this approach is similar to @Shahar's. The difference is that instead of some, I delegate a lot more work to the RegExp test method which is a bit faster.

Matching the third sentence comes with a performance cost.

const match = (regex, sentence) => {
    return regex.test(sentence
       .replace(/ /g, '') // <-- string3 will not match by removing this line, performance will be better
    );
};
    
const words = ["champ", "winner", "world"];
const string = "I am a champ";    // it match
const string2 = "I am achamp";    // it match
const string3 = "I am a win ner"; // it match
const string4 = "I am not able to figure this"; // no

const regex = new RegExp(words.join('|'), "i");   
console.log(match(regex, string))  // true
console.log(match(regex, string2)) // true
console.log(match(regex, string3)) // true
console.log(match(regex, string4)) // false

Bench test

I've tested at JSBEN.CH the 3 current RegExp answers: @Stan's, @Shahar's and mine here

Check the best one by yourself ;)

user_16574650

A very simple solution that splits the string and checks if its length is greater than 1:

var words = ["champ", "winner", "world"];

var string = "I am a champ";
var string2 = "I am achamp";
var string3 = "I am a winner";
var string4 = "I am not able to figure this";

console.log(checkWords(words, string));
console.log(checkWords(words, string2));
console.log(checkWords(words, string3));
console.log(checkWords(words, string4));

function checkWords(words, string) {
  var matches = false;
  words.forEach(word => {
    var split = string.split(word);
    if (split.length > 1) {
      matches = true;
    }
  })
  return matches;
}

I didn't see this approach in any of the current answers (who use regex) and I think it's the easiest way.

user_133311550
Related