任何人都可以建议一个适当的数据结构来保存一个字典，让我可以查询在特定位置具有特定字母的单词（项目）的存在吗？例如，确定哪些单词（如果有）在 x、y、z 位置具有字母 a、b、c。插入不必特别有效。
这基本上是拼字游戏的问题（我也有与字母相关的分数，但这不需要我们关心）。我怀疑生物信息学家以序列比对的名义研究了同样的问题。就速度而言，最先进的技术是什么？
问问题
310 次
1 回答
2
如果您正在尝试构建一个非常快速的拼字游戏播放器，您可能需要查看专门为此目的设计的GADDAG数据结构。从本质上讲，GADDAG 是一个压缩的 trie 结构（具体来说，它是一个修改后的 DAWG），它可以让您向外探索并找到可以由一组特定字母组成的所有单词，这些单词的哪些字母必须在什么位置受到限制，以及找到的字符串的总长度。
有关 GADDAG 的 Wikipedia 文章更深入地介绍了结构并链接到有关该主题的原始论文。您可能还想将 DAWG 作为起点。
希望这可以帮助！
于 2012-12-27T08:41:06.207 回答