algorithm - 查找具有特定长度并由某些字母组成的短语

Question

假设我有一个包含 100 万个单词的列表。我有我需要找到的短语的长度，并且我知道这个词最多可以由其他 3 个词组成，例如Queen of England，有 14 个字母，字母是adeeefglnnnoqu。

问题是，给定这么大的字典，首先我必须搜索第一个单词，它可以有 1 到 14 个字母，然后是第二个单词（如果第一个单词没有 14 个字母） ，然后是第三个词。

给定字典大小为 100 万个单词，第一个循环必须遍历所有单词，然后第二个循环也需要遍历所有 100 万个单词，因为它必须消除第一个单词消耗的字母，并遍历所有 100 万个单词，找出那些仍然有效但没有第一个单词消耗的字母的单词。第三个循环会更容易一些，因为我知道单词 ( 14 - word1.length - word2.length) 的确切长度。

至少，仅考虑前 2 个循环，即 1,000,000,000,000 次迭代。有一个更好的方法吗？

这个问题与语言无关，因为我并不真正关心我需要使用什么语言来解决这个问题。

Answer 1

您可以通过过滤掉明显不属于的单词来加快该过程，即在短语中找不到字母的单词。一旦您预先过滤了 1M 列表，您最终应该会得到更短的子列表。在该子列表上运行您的算法应该会快得多，因为它是一种O(N^2)算法：即使您将列表缩小到单词的 10%（我希望您得到的单词比这要少得多），您也会得到 100-折叠改进。只要不丢弃潜在的匹配项，列表就有“误报”是可以的。

以下是如何进行预过滤：对于每个单词，构建其“签名”，一个 26 位数字，为单词中存在的每个字母设置一个位至少一次（字母编号为 0 到 25，忽略案子）。例如，该词"Queen"的签名将第 4、13、16 和 20 位设置为 1。

现在为您的三词短语构造一个签名，并使用它来过滤 1M 单词的列表：如果OR单词的签名和短语的签名按位等于短语的签名，则保留该单词；否则，扔掉它。

您的过滤列表应该更短，因此您的O(N^2)算法应该运行得更快。