"""A Trie/Prefix Tree is a kind of search tree used to provide quick lookupof words/patterns in a set of words. A basic Trie however has O(n^2) space complexitymaking it impractical in practice. It however provides O(max(search_string, length of longest word)) lookuptime making it an optimal approach when space is not an issue."""class TrieNode:def __init__(self):self.nodes = dict() # Mapping from char to TrieNodeself.is_leaf = Falsedef insert_many(self, words: [str]): # noqa: E999 This syntax is Python 3 only"""Inserts a list of words into the Trie:param words: list of string words:return: None"""for word in words:self.insert(word)def insert(self, word: str): # noqa: E999 This syntax is Python 3 only"""Inserts a word into the Trie:param word: word to be inserted:return: None"""curr = selffor char in word:if char not in curr.nodes:curr.nodes[char] = TrieNode()curr = curr.nodes[char]curr.is_leaf = Truedef find(self, word: str) -> bool: # noqa: E999 This syntax is Python 3 only"""Tries to find word in a Trie:param word: word to look for:return: Returns True if word is found, False otherwise"""curr = selffor char in word:if char not in curr.nodes:return Falsecurr = curr.nodes[char]return curr.is_leafdef print_words(node: TrieNode, word: str): # noqa: E999 This syntax is Python 3 only"""Prints all the words in a Trie:param node: root node of Trie:param word: Word variable should be empty at start:return: None"""if node.is_leaf:print(word, end=' ')for key, value in node.nodes.items():print_words(value, word + key)def test():words = ['banana', 'bananas', 'bandana', 'band', 'apple', 'all', 'beast']root = TrieNode()root.insert_many(words)# print_words(root, '')assert root.find('banana')assert not root.find('bandanas')assert not root.find('apps')assert root.find('apple')test()
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。