Implementing A Trie To Support Autocomplete In Python

I'm trying to implement a data structure that supports autocomplete on a website. I've managed to implement an iterative version of a Trie. It supports the two primary methods of a

Solution 1:

You could just implement a generator that iterates over the Trie according to prefix the same way as other methods do. Once you've found the node at the end of the prefix you can use recursive generator with yield from to iterate over the sub trie while keeping track of the prefix and yielding it when terminal node is found:

classTrieNode:
    def__init__(self):
        self.end = False
        self.children = {}

    defall_words(self, prefix):
        if self.end:
            yield prefix

        for letter, child in self.children.items():
            yieldfrom child.all_words(prefix + letter)

classTrie:
    # existing methods heredefall_words_beginning_with_prefix(self, prefix):
        cur = self.root
        for c in prefix:
            cur = cur.children.get(c)
            if cur isNone:
                return# No words with given prefixyieldfrom cur.all_words(prefix)

trie = Trie()
trie.insert('foobar')
trie.insert('foo')
trie.insert('bar')
trie.insert('foob')
trie.insert('foof')

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

Output:

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

Solution 2:

classTrie:

    def__init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.end = "#"defwords_with_prefix(self, prefix: str):
        '''
        return all possible words with common prefix
        '''
        node = self.root
        for c in prefix:
            if c notin node:
                return []
            node = node[c]
        ans = []
        self._words_with_prefix_helper(node, prefix, ans)
        return ans

    def_words_with_prefix_helper(self, node, prefix, ans):
        for k in node:
            if k == self.end:
                ans.append(prefix)
                continue
            self._words_with_prefix_helper(node[k], prefix + k, ans)

complete implementation

Solution 3:

from collections import defaultdict


classTrieNode:
    def__init__(self):
        self.node = defaultdict(TrieNode)
        self.is_word = FalseclassTrie:
    def__init__(self):
        self.root = TrieNode()

    definsert(self, words):
        curr = self.root

        for char in words:
            curr = curr.node[char]
        curr.is_word = Truedefsearch(self, word):
        curr = self.root
        for char in word:
            if char notin curr.node:
                returnFalse
            curr = curr.node[char]
        return curr.is_word

    defdfs(self, node, word, word_list):
        if node.is_word == True:
            word_list.append(word)
        for a, n in node.node.items():
            self.dfs(n, word + a, word_list)

    defauto_complete(self, word_to_search, word_list):
        temp_word = ""
        curr = self.root
        for char in word_to_search:
            if char notin curr.node.keys():
                print("Invalid Input")
            else:
                temp_word += char
                curr = curr.node[char]
        self.dfs(curr, temp_word, word_list)
        print(word_list)