A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

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 is a basic autocomplete method that we can drop into our Trie class:

def autocomplete(self, prefix):
  currentNode = self.search(prefix)
  if not currentNode:
    return None
  return self.collectAllWords(currentNode)

Yes, that’s it. By using our search method and collectAllWords 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 search method doesn’t ...