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 search method doesn’t find the prefix in the trie, the search method returns None, and so our method does as well.

However, if the prefix is found in the trie, the search method returns the node in the trie that represents the final character in the prefix. We noted earlier that we could have simply had the search method return True once it finds the word. The reason why we had it return the final node was so that we could use the search method to help us with the autocomplete feature.

Our autocomplete method continues by calling the collect_all_words method on the node returned by the search method. This finds and collects all words that stem from that final node, which represents all the complete words that can be appended to the original prefix to form a word.

Our method finally returns an array of all possible endings to the user’s prefix, which we could then display to the user as possible autocomplete options.