我有一段代码,可以在给定一个字符串时构建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')))
我怎么修理它
每次插入后,您都不会将
curr
重置回根目录,因此您将在最后一个单词停止的位置插入下一个单词。您可能需要以下内容:不过,我还是要把它打破。我认为
insert
函数做的太多了,不应该处理多个字符串。我会把它改成这样:现在这不是问题,因为每个
insert
都是一个独立的调用,您不能忘记重置curr
相关问题 更多 >
编程相关推荐