javascript - 在数组中搜索字符串匹配

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);
}

更新:我尝试了以下解决方案但仍然停止工作我正在研究谷歌音频到语音所以它不断地运行一些语音所以句子数组一次又一次地触发我认为这就是它在之后卡住的原因一些点

更新 2: 在上面的示例中，我搜索单个词，即“India”，但如果我搜索的是多个词，比如它是一个人名，如“Neil Armstrong”，那么拆分方法将不会工作。

Answer 1

Array#indexOf 是一个 O(n) 操作 - 解释器必须遍历整个数组，最坏的情况，看看是否有匹配项.当在循环中完成时，这会将计算复杂度增加到 O(n ^ 2)，这会很慢。

您可以改用 Set - 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 使代码更加简洁。

如果您希望匹配的项目由两个词组成，则还要匹配每个相邻的 2 个词:

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))
);