英文:
How to iterate over each word in a Trie using __iter__()and __next__() functions and generators in Python
问题
我有一个如下结构的 Trie。我试图编写一个迭代器和 next 函数，以便在 Trie 中迭代每个单词，然后在完成时引发 StopIteration，但我在理解这两个函数应该如何工作方面遇到了困难。我知道我需要使用 yield 而不是简单返回，但我不确定如何实现它。感谢任何帮助。
class TrieNode:
def __init__(self, char):
self.char = char
self.children = {}
self.is_word = False
class TrieDictionary:
def __init__(self):
self.root = TrieNode("")
def __iter__(self):
return self
def __next__(self):
# 从迭代器获取下一个单词，如果没有更多单词，则停止迭代
英文:
I have a Trie that is structured below. I am trying to write an iterator and next function that will iterate over each word in the Trie and then raise StopIteration once it is completed but I'm struggling to understand how these two functions are supposed to work. I know that I need to use yield instead of simply returning but I'm not sure how to go about implementing it. Appreciate any help.
class TrieNode:
def __init__(self, char):
self.char = char
self.children = {}
self.is_word = False
class TrieDictionary:
def __init__(self):
self.root = TrieNode("")
def __iter__(self):
return self
def __next__(self):
# get next word from iterator and stop iteration if no more words
答案1
得分: 1
class TrieNode:
def __iter__(self):
if self.is_word:
yield ""
for ch, child in self.children.items():
for word in child:
yield ch + word
class TrieDictionary:
def __iter__(self):
yield from self.root
# demo
tree = TrieDictionary()
tree.add("sensitive").add("sense").add("senior").add("sentiment").add("sensible")
print(*tree)
英文:
You could make a generator on the TreeNode class, then you don't really need to worry about __next__:
class TrieNode:
def __init__(self, char):
self.char = char
self.children = {}
self.is_word = False
def __iter__(self):
if self.is_word:
yield ""
for ch, child in self.children.items():
for word in child:
yield ch + word
class TrieDictionary:
def __init__(self):
self.root = TrieNode("")
def add(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode(ch)
node = node.children[ch]
node.is_word = True
return self
def __iter__(self):
yield from self.root
# demo
tree = TrieDictionary()
tree.add("sensitive").add("sense").add("senior").add("sentiment").add("sensible")
print(*tree)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论