传递要放入trie的字符串列表

Question

我有一段代码，可以在给定一个字符串时构建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:
    def __init__(self):
        self.root = TrieNode()
    def __init__(self):
        self.root = TrieNode()

    def insert(self, words):
        curr = self.root
        #the line I added to read the words from a list is below
        for word in words:
            for letter in word:
                node = curr.children.get(letter)
                if not node:
                    node = TrieNode()
                    curr.children[letter] = node
                curr = node
            curr.end  = True


    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)

这是我用来将所有内容插入树中的代码：

lst = ['foo', 'foob', 'foobar', 'foof']
trie = Trie()
trie.insert(lst)

我得到的输出是

['foo', 'foofoob', 'foofoobfoobar', 'foofoobfoobarfoof']

我希望得到的输出是

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

这是我用来获取输出的行（为了再现性，如果您需要运行代码），它返回以特定前缀开头的所有单词：

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

我怎么修理它

Answer 1

每次插入后，您都不会将curr重置回根目录，因此您将在最后一个单词停止的位置插入下一个单词。您可能需要以下内容：

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

不过，我还是要把它打破。我认为insert函数做的太多了，不应该处理多个字符串。我会把它改成这样：

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 insert_many(self, words):
    for word in words:
        self.insert(word)  # Just loop over self.insert

现在这不是问题，因为每个insert都是一个独立的调用，您不能忘记重置curr