java - 用另一组字母检查单词中字母的算法和数据结构

Question

我有一本包含 200,000 个单词的字典和一组字母。我需要一种算法来检查一个单词的所有字母是否都在该组字母中。一个一个地查单词，速度很慢。因为有大量的单词要处理，所以我需要一个数据结构来做这件事。有任何想法吗？谢谢!

例如:我有一组字母{b,g,e,f,t,u,i,t,g,n,c,m,m,w,c,s}，我想检查是否“大”和“浅黄色”两个词。 “big”的所有字母都是原始集合的子集，然后“big”是我想要的，而“buff”不是我想要的，因为原始集合中只有一个“f”。这就是我想做的。

Answer 1

这是为了像 Scrabble 或 Boggle 这样的东西，对吧？那么，您要做的是通过排序每个单词中的字母来预先生成您的字典。所以，word 变成了 dorw。然后你把所有这些都推到一个 Trie 数据结构中。因此，在您的 Trie 中，序列 dorw 将指向值 word。

[请注意，由于我们对单词进行了排序，它们失去了唯一性，因此一个排序后的单词可以指向多个不同的单词。 即您的 Trie 需要在其数据节点存储列表或数组]

如果以后需要快速加载它而无需所有排序步骤，则可以将此结构保存出来。

然后您要做的就是获取您输入的字母并对它们进行排序。然后你开始递归地遍历你的 Trie。如果当前字母与 Trie 中的现有路径相匹配，则遵循该路径。因为您可以有未使用的字母，所以您也允许丢弃当前字母。

就这么简单。任何时候你在你的 Trie 中遇到一个有值的节点，这个词你可以用你用来到达那里的字母组成。您只需在找到这些词时将它们添加到列表中，当递归完成时，您就找到了每个可能的词。

如果您在输入中有重复的字母，您可能需要额外的逻辑来防止给出同一个词的多个实例(除非您想要)。在“省略”一个字母(您只需跳过所有重复的字母)到下一个字母的步骤中可以调用该逻辑。

---

[edit] 你似乎想做相反的事情。我上面的解决方案找到了可以由一组字母组成的所有可能的单词。但是你想测试一个特定的词，看看它是否被允许，给定你的字母集。

这很简单。

将可用字母存储为直方图。也就是说，对于每个字母，您存储您拥有的数字。然后，您遍历测试单词中的每个字母，边走边构建一个新的直方图。一旦您的直方图桶之一超过了可用字母中的值，就无法生成该词。如果你一路走到最后，你就可以成功地造出这个词。