展开实际上是正确的，因为有许多不同的方法可以实现Trie。对于大型，可伸缩的特里，嵌套字典可能会变得很麻烦-或至少在空间上效率低下。但是，由于你才刚刚入门，因此我认为这是最简单的方法；你trie只需几行就可以编写一个简单的代码。首先，一个构造特里的函数：
>>> _end = '_end_'>>> >>> def make_trie(*words):... root = dict()... for word in words:... current_dict = root... for letter in word:... current_dict = current_dict.setdefault(letter, {})... current_dict[_end] = _end... return root... >>> make_trie('foo', 'bar', 'baz', 'barz'){'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 'z': {'_end_': '_end_'}}}, 'f': {'o': {'o': {'_end_': '_end_'}}}}如果你不熟悉
setdefault，它只会在字典中查找一个键（此处为
letter或
_end）。如果键存在，则返回关联的值；否则，返回0。如果不是，它将为该键分配一个默认值并返回值（
{}或_end）。（就像它的一个版本一样
get，也会更新字典。）
接下来，一个测试单词是否在特里的函数：
>>> def in_trie(trie, word):... current_dict = trie... for letter in word:... if letter not in current_dict:... return False... current_dict = current_dict[letter]... return _end in current_dict... >>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'baz')True>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barz')True>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barzz')False>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'bart')False>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'ba')False我将把插入和拔出留给你作为练习。
当然，Unwind的建议不会难得多。在速度方面可能存在一点缺点，即找到正确的子节点需要进行线性搜索。但是搜索将限于可能的字符数-如果包括，则为27 _end。而且，按照他的建议，创建大量节点并按索引访问它们并不会获得任何好处。你最好只嵌套列表。
最后，我要补充一点，创建有向无环词图（DAWG）会有些复杂，因为你必须检测当前词与结构中另一个词共享后缀的情况。实际上，这可能会变得相当复杂，具体取决于你要如何构造DAWG！你可能需要学习一些有关Levenshtein 距离的知识才能正确处理。
