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:

amazon prime
amazing spider man

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.

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

Autocomplete with trie (YouTube)
Java Coding Interview Pocket Book (2nd Edition)

Comments are closed