有效地检查一个单词是否符合一个集合中的模式 (Python)

Question

我有一套简单的全局模式和完整的单词，比如：

s = set(['ALE', 'BREAD*', 'BREAKFAST*', 'BROTH' ...])

我还有一大串单词。我想检查这个列表中的每个单词是否匹配a）集合中的全局模式或b）集合中的一个单词。在

如果没有全球化模式，我会做一些类似的事情：

^{pr2}$

但是由于该集合也包含全局模式，所以如果我想将“BREADY”与“BREAD*”匹配，它将找不到匹配项

我能想到的唯一方法是使用嵌套的for循环将每个单词与集合中的每个模式进行比较。有没有一种方法可以检查集合中每个单词是否都有匹配项，而不必与集合中的每个元素进行比较？在

Answer 1

应该将要匹配的完整字符串与要匹配的前缀分开存储。对于您的前缀，进一步将它们划分为长度相等的前缀集（即一组长度为1的前缀，一组长度为2的前缀，等等）。在

即

fullstrings = set(["BREAKFAST", "LUNCH", "DINNER", ...])
prefixes_by_length = {} # dict of length -> prefix string
...
prefixes_by_length[4] = set(["CORN", "DESK", ...])
prefixes_by_length[5] = set(["BREAD", "TABLE", ...])

完整字符串匹配很简单-只需检查word in fullstrings。在

对于前缀，将分别检查每个长度，从长度1到要匹配的最大前缀长度。对于每个长度n，请检查word[:n] in prefixes_by_length[n]。在

如果你有很多前缀的话，这比每次循环遍历所有前缀要有效得多。在

^{pr2}$