A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

Completing Autocomplete

We’re finally ready to implement our autocomplete feature. In fact, we’ve pretty much done all the legwork already. All we need to do is put the pieces together.

Here’s a basic autocomplete method that we can drop into our Trie class:

def autocomplete(self, prefix):
    current_node = self.search(prefix)

    if not current_node:
        return None

    return self.collect_all_words([], current_node)

Yes, that’s it. By using our search method and collect_all_words method together, we can autocomplete any prefix. Here’s how this works.

The autocomplete method accepts the prefix parameter, which is the string of characters the user begins typing in.

First, we search the trie for the existence of the prefix. If the