检查列表中是否有任何子字符串在另一个字符串列表中的最有效方法

Question

我有两个列表，一个是单词，另一个是字符组合。什么是只返回与列表中任何内容都不匹配的组合的最快方法？在

我试着让它尽可能的精简，但是当它使用3个字符进行组合时仍然非常慢（对于4个字符，它最多可以达到290秒，甚至不会尝试5个字符）

下面是一些示例代码，目前我正在将所有单词转换为一个列表，然后在字符串中搜索每个列表值。在

#Sample of stuff
allCombinations = ["a","aa","ab","ac","ad"]
allWords = ["testing", "accurate" ]

#Do the calculations
allWordsJoined = ",".join( allWords )
invalidCombinations = set( i for i in allCombinations if i not in allWordsJoined )

print invalidCombinations
#Result: set(['aa', 'ab', 'ad'])

我只是想知道有没有更好的方法来处理这个问题？使用3个字母的组合，有18278个列表项要搜索，而对于4个字母，则达到了475254个，因此目前我的方法还不够快，尤其是当单词列表字符串大约有100万个字符时。在

如果需要整个字符串，Set.intersection似乎是一个非常有用的方法，因此肯定有类似于搜索子字符串的方法。在

Answer 1

首先想到的是，您可以通过检查当前组合与已经“无效”的组合来优化查找。一、 e.如果ab无效，那么ab。？也将无效，没有必要检查。在

还有一件事：试着用

for i in allCombinations:
    if i not in allWordsJoined:
        invalidCombinations.add(i)

而不是

^{pr2}$

我不确定，但是更少的内存分配对于实际的数据运行来说可能是一个小小的提升。在

Answer 2

看一个集合是否包含一个项是O（1）。您仍然需要迭代组合列表（有些例外情况除外）。如果你的单词没有“a”，它就不会有任何其他包含“a”的组合。你可以使用一些树状的数据结构来与你的原始单词集进行比较。在

你不应该把你的单词表转换成一个字符串，而是一个集合。你应该得到O（N），其中N是组合的长度。在

另外，我喜欢Python，但它不是最快的语言。如果这是您需要做的唯一任务，并且它需要非常快，并且您无法改进算法，那么您可能需要检查其他语言。你应该能够很容易地建立一些原型来了解不同语言在速度上的差异。在