首先，让我们来看看问题的限制条件。您希望在数据结构中存储一个单词列表，以有效支持“字谜”问题。也就是说，对于一个由n个字母组成的“架子”，该单词列表中可以从该架子中制作出所有n个或更少字母的单词。单词列表将约有400K个单词，因此未压缩时可能为1到10兆字节。
trie（字典树）是解决这个问题的经典数据结构，因为它结合了内存效率和搜索效率。对于约有400K个适当长度的单词的单词列表，您应该能够将trie保留在内存中。(与使用B-Tree的解决方案相比，后者需要将大部分树保存在磁盘上，因为它太大而无法一次性放入内存中。)
Trie基本上只是一个26叉树(假设您使用罗马字母表)，每个节点都有一个字母和每个节点上额外的一个位表示它是否是单词的结尾。
现在，让我们来设计这个数据结构:
class TrieNode
{
char Letter;
bool IsEndOfWord;
List<TrieNode> children;
}
当然，这只是一个草图；你可能想要为它们创建适当的属性访问器和构造函数等等。另外，也许平面列表不是最好的数据结构；也许某种类型的字典更好。我的建议是先让它工作起来，然后测量其性能，如果性能不可接受，再尝试进行改进。
你可以从一个空的trie开始：
TrieNode root = new TrieNode('^', false, new List<TrieNode>())
也就是说，这是代表单词开头的“根”trie节点。
如何添加“AA”这个单词，它是Scrabble词典中的第一个单词？首先，为第一个字母创建一个节点：
root.Children.Add('A', false, new List<TrieNode>())
好的，我们现在的 trie 树是：
^
|
A
现在添加一个节点表示第二个字母：
root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()))
我们现在的trie树是
^
|
A
|
A$ -- we notate the end of word flag with $
很好。现在假设我们想添加AB。我们已经有了一个节点代表"A"，所以将"B$"节点添加到它上面：
root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>())
现在我们有了
^
|
A
/ \
A$ B$
继续保持这样的进展。当然，你将不再写"root.Children[0]..."，而是编写一个循环来搜索trie，查看是否存在所需的节点，如果不存在，则创建它。
要将trie存储在磁盘上--坦白地说，我会将单词列表存储为纯文本文件，并在需要时重新构建trie。这不应该花费超过30秒的时间，然后您可以在内存中重复使用trie。如果您确实想以更像trie的格式存储trie，那么想出一种序列化格式应该不难。
为了搜索匹配rack的trie，思路是探索trie的每个部分，但修剪掉无法与rack匹配的区域。如果rack上没有任何"A"，则无需深入任何"A"节点。我在您之前的问题中勾勒出了搜索算法。
我有一个功能性的持久trie实现，我一直想博客上发布一下，但一直没有实现。如果我最终发布了，我会更新这个问题。
