python - 实现Trie以支持Python中的自动完成功能

我正在尝试实现一种支持网站上自动完成功能的数据结构。
我设法实现了Trie的迭代版本。它支持在Trie中添加和搜索的两种主要方法。
但是，现在我需要添加一个方法，该方法返回以以下前缀开头的所有单词。有人可以帮我弄这个吗。

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        curr = self.root
        for letter in word:
            node = curr.children.get(letter)
            if not node:
                node = TrieNode()
                curr.children[letter] = node
            curr = node
        curr.end = True

    def search(self, word):
        curr = self.root
        for letter in word:
            node = curr.children.get(letter)
            if not node:
                return False
            curr = node
        return curr.end

    def all_words_beginning_with_prefix(self, prefix):
        #I'm not sure how to go about this one.

最佳答案

您可以实现一个生成器，该生成器按照与其他方法相同的方式根据前缀对Trie进行迭代。一旦在前缀末尾找到了节点，就可以使用带有yield from的递归生成器来遍历子Trie，同时跟踪前缀并在找到终端节点时产生该前缀:

class TrieNode:
    def __init__(self):
        self.end = False
        self.children = {}

    def all_words(self, prefix):
        if self.end:
            yield prefix

        for letter, child in self.children.items():
            yield from child.all_words(prefix + letter)

class Trie:
    # existing methods here
    def all_words_beginning_with_prefix(self, prefix):
        cur = self.root
        for c in prefix:
            cur = cur.children.get(c)
            if cur is None:
                return  # No words with given prefix

        yield from cur.all_words(prefix)

trie = Trie()
trie.insert('foobar')
trie.insert('foo')
trie.insert('bar')
trie.insert('foob')
trie.insert('foof')

print(list(trie.all_words_beginning_with_prefix('foo')))

输出:

['foo', 'foob', 'foobar', 'foof']

关于python - 实现Trie以支持Python中的自动完成功能，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46038694/