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

一个 Set 是快速测试成员资格的理想结构:

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一次并将其作为参数传递。

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