data-structures - 什么数据结构用于维护命运之轮中的候选词？

Question

命运之轮的背景，对于那些不熟悉的人来说:在命运之轮游戏中，玩家最初会看到一组空白，代表隐藏字母的单词。 (所以玩家知道每个单词的长度，但不知道单词包含哪些字母。)随着游戏的进行，玩家猜字母；如果短语包含该字母，则显示该字母在短语中的所有位置。例如，游戏(带有隐藏短语“堆栈溢出”)最初将表示为 ????? ????????，猜到字母“o”后，游戏会显示???????哦？？？？哇。

为简单起见，假设我们的游戏只包含一个隐藏词。我将使用什么数据结构来保存该单词的所有可能候选者？ (我正在玩一个 AI 来选择接下来要猜测的字母，所以为了做出选择，我希望能够计算统计数据，比如剩下的候选字母中最常见的字母。)要清楚，最初我知道我的单词包含 N 个字母，然后我学习了单词中各种字母的位置，以及单词不包含哪些字母。

Good algorithm and data structure for looking up words with missing letters? 上也有类似的问题，但我认为这个问题略有不同，因为我有两个以上的空白，而且我也在迭代地修剪我的候选列表(而该问题似乎只使用一次搜索)。我目前的想法是只维护一个候选单词列表，初始化为所有英语单词(最多应该有 300k-500k 个单词)，然后(对那个问题采取类似的方法)使用正则表达式迭代地修剪这个候选列出我猜更多的字母，但我很好奇是否有更好的数据结构或算法。

Answer 1

您应该首先根据大小拆分单词。在每个尺寸中，http://en.wikipedia.org/wiki/Trie似乎是一个好的开始。您将立即修剪整个子树，并且您可以通过仅在每个节点处翻转一个标志来保持树的完整，无论在当前游戏中是否不考虑以该节点为根的子树。