Autocomplete with trie – Code

Autocomplete is a feature that search box returns the suggestions based on what you have typed. Autocomplete with trie provides an implementation of auto-complete by using data structure trie.

What is trie? A trie is a tree-like data structure in which every node stores a character. After building the trie, strings or substrings can be retrieved by traversing down a path of the trie. normally, Trie can be implemented with HashMap, ArrayList or LinkedList. Here I use LinkedList to implement trie.

To implement autocomplete, we use DFS (depth first search). We start from root, navigate to the end of prefix. From there, we call the helper method to find all the substrings with the same prefix.

Amazon Interview Question:
Implement autocomplete using trie. When searching “amaz”, it should return words that start with “amaz” such as “amazon”, “amazon prime”, “amazing” etc.

Java Code:

Output:
amazon
amazon prime
amazing
amazing spider man
amazed

O Notation:
Time complexity: O(n), n is the longest string, e.g “amazing spider man” in this example.
Space complexity: O(n*m), m is the number of words in trie.

Note:
If you have any questions or want to put comments, please post at youtube. I will answer you!

Acition Items:
Download AutocompleteWithTrie.java
Autocomplete with trie tutorial
The complete list of coding interview questions

Comments are closed