JavaScript：将字符串与所有必需的字符匹配

Question

我正在寻找一个正则表达式模式来匹配包含所有必需字符列表的字符串。例如，如果我的要求是"abc"：匹配："abacus", "back", "cab"。不匹配："abs", "car", "banana"。到目前为止，我已经提出了这些（非正则表达式）方法：function testA(requiredChars, checkString) {  return requiredChars.split('').every(char => checkString.indexOf(char) !== -1)}function testB(requiredChars, checkString) {  for (let char of requiredChars.split('')) {    if (checkString.indexOf(char) == -1) return false  }  return true}tests = [ 'abacus', 'back', 'cab', 'abs', 'car', 'banana' ]tests.forEach(word => {  console.log(word, testA('abc', word), testB('abc', word))})// abacus true true// back true true// cab true true// abs false false// car false false// banana false false我喜欢第一个更小，但不幸的是第二个更快。使用正则表达式可以更快地完成这项工作，还是我应该在领先时退出？

Answer 1

ASet是快速测试成员资格的理想结构：

const containsChars = (chars, s) => {

  const lookup = new Set(s);

  return [...chars].every(e => lookup.has(e));

};

tests = ['abacus', 'back', 'cab', 'abs', 'car', 'banana'];

tests.forEach(word => console.log(word, containsChars('abc', word)));

这几乎肯定会比正则表达式更有效，正则表达式不太适合此类任务。O(checkString.length * requiredChars.length)由于嵌套indexOf调用，您现有的解决方案在二次时间内运行，checkString对于每个requiredChars. 但是构造一个集合是一次性的，使得整个算法为 O(n)。

但是，如果您的输入总是很小，则在每次调用时为 set 对象分配内存的开销将超过它的好处。如果是这种情况，请坚持使用现有的解决方案。如果您总是与相同的 进行比较requiredChars，您可以尝试构建Set一次并将其作为参数传入。

但是，如果这不是经常在循环中调用的热代码，请避免过早优化并选择您认为可读的解决方案（尽管在这种情况下它们几乎都相同）。在您通过分析确定它们是瓶颈之前，过度优化功能通常会适得其反。

Answer 2

它可以用正则表达式来完成，但不会更快——你必须对每个字符进行预测，这很丑陋：

const dedupe = str => [...new Set(str)].join('');

const test = (requiredChars, checkString) => {

  const requiredPatterns = [...requiredChars].map(char => `(?=.*${char})`);

  const pattern = new RegExp(`^${requiredPatterns.join('')}`);

  return pattern.test(checkString);

};

tests = [ 'abacus', 'back', 'cab', 'abs', 'car', 'banana' ]

tests.forEach(word => {

    console.log(word, test('abc', word))

});

这不是很好。使用您当前的策略，除了使用 Set 而不是数组 - Set.hasis O(1)，而Array.indexOf和Array.includesare O(n)（如另一个答案所示）。