autocomplete_using_trie.py

from __future__ importannotations

END="#"


classTrie:
def__init__(self) ->None:
self._trie: dict= {}

definsert_word(self, text: str) ->None:
trie=self._trie
forcharintext:
ifcharnotintrie:
trie[char] = {}
trie=trie[char]
trie[END] =True

deffind_word(self, prefix: str) ->tuple|list:
trie=self._trie
forcharinprefix:
ifcharintrie:
trie=trie[char]
else:
return []
returnself._elements(trie)

def_elements(self, d: dict) ->tuple:
result= []
forc, vind.items():
sub_result= [" "] ifc==ENDelse [(c+s) forsinself._elements(v)]
result.extend(sub_result)
returntuple(result)


trie=Trie()
words= ("depart", "detergent", "daring", "dog", "deer", "deal")
forwordinwords:
trie.insert_word(word)


defautocomplete_using_trie(string: str) ->tuple:
"""
 >>> trie = Trie()
 >>> for word in words:
 ... trie.insert_word(word)
 ...
 >>> matches = autocomplete_using_trie("de")
 >>> "detergent " in matches
 True
 >>> "dog " in matches
 False
 """
suffixes=trie.find_word(string)
returntuple(string+wordforwordinsuffixes)


defmain() ->None:
print(autocomplete_using_trie("de"))


if__name__=="__main__":
importdoctest

doctest.testmod()
main()