поиск в массиве для совпадения строк

Question

Что у меня есть

var sentence = 'My country is India';
var array = ['Intel,' 'Goa', 'Green Day', 'India', 'Ice', 'India'];

Результат мне нужен

  index = array.indexOf(sentence); // it should return 3

И это то, что я пытался это работает, но это очень замедляется, зависает и перестает работать при использовании больших данных

words = sentence.split(' ');
var i;
for (i = 0; i < words.length; i++) {
    w = words[i];
    a = array.indexOf(w);
    console.log(a);
}

Обновление : я пробовал приведенные ниже решения, но все еще прекращаю работать, я работаю над звуком Google в речь, поэтому он постоянно запускается, кто-то говорит так что массив предложений снова и снова срабатывает, я думаю, именно поэтому его замораживание после некоторой точки

Обновление 2: В приведенном выше примере я ищу одно слово, то есть "Индия", но что если я его больше чем одно слово, например, если это персональное имя типа «Нил Армстронг», то метод разделения не будет работать.

Answer 1

Array#indexOf - это операция O(n) - интерпретатор должен выполнить итерацию по всему массиву, в худшем случае, чтобы увидеть, есть ли совпадение или нет. Когда все сделано в oop, это увеличивает вычислительную сложность до O(n ^ 2), что будет медленным.

Вместо этого можно использовать набор - Set#has имеет сложность O(1) (уменьшая общее сложность до O(n)):

var sentence = 'My country is India';
var array = ['Intel', 'Goa', 'Green Day', 'India', 'Ice'];

const words = new Set(sentence.split(' '));
console.log(
  array.findIndex(word => words.has(word))
);

Или объект (поиск ключа объекта тоже O(1)):

var sentence = 'My country is India';
var array = ['Intel', 'Goa', 'Green Day', 'India', 'Ice'];

const words = Object.fromEntries(
  sentence.split(' ').map(key => [key])
);
console.log(
  array.findIndex(word => words.hasOwnProperty(word))
);

Узнайте, как вы также можете использовать findIndex, чтобы сделать код гораздо более кратким.

Если элемент, который вы хотите сопоставить, состоит из два слова, также соответствуют каждому вхождению двух слов рядом друг с другом:

var sentence = 'My country is Green Day';
var array = ['Intel', 'Goa', 'Green Day', 'India', 'Ice'];

const words = new Set(sentence.split(' '));
const pattern = /(?=(\S+ \S+))/g;
while (true) {
  const match = pattern.exec(sentence);
  if (!match) {
    break;
  }
  words.add(match[1]);
  pattern.lastIndex++;
}
console.log(
  array.findIndex(word => words.has(word))
);

Для более общего решения вы можете проверить входной массив, чтобы определить, какое количество слов вам нужно собрать, а затем для каждого числа перебрать слова предложения, чтобы добавить их в набор:

var sentence = 'My country is Green Day';
var array = ['Intel', 'Goa', 'Green Day', 'India', 'Ice'];

const combinationsNeeded = new Set();
for (const substr of array) {
  combinationsNeeded.add(substr.split(' ').length);
}
const wordsSet = new Set();
const sentenceWords = sentence.split(' ');
for (const comb of combinationsNeeded) {
  let endIndex = comb;
  for (let i = 0; i + comb <= sentenceWords.length; i++) {
    // uncomment the below to see all the words wordsSet gets
    // console.log(sentenceWords.slice(i, i + comb).join(' '));
    wordsSet.add(sentenceWords.slice(i, i + comb).join(' '));
  }
}

console.log(
  array.findIndex(substr => wordsSet.has(substr))
);

Answer 2

const sentence = 'My country is India';
const array = ['Intel', 'Goa', 'Green Day', 'India', 'Ice', 'India'];
const my_vals =  array.map((val, inx)=> sentence
                     .match(val)? inx : -1)
                     .filter(x => x>-1);

это вернет массив со всеми соответствующими индексами.

[3, 5]

Answer 3

Вы можете отсортировать оба массива и выполнить бинарный поиск для каждого из элементов.