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.

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. First we define the TrieNode, which includes data, children and isEnd (to mark whether this node is the last node of a word). Children can be implemented with Array, LinkedList, and HashMap. Each implementation has its pros and cons. Take a loot at Doodle below to see the differences. Next we define Trie class, in which there are methods such as insert, search etc.

To implement autocomplete, we start from root, navigate to the end of prefix. From there, we call the recursion function method to find all the nodes branched from the last node of prefix. This method is the same as pre-order of the tree from the root. Therefore the complexity is O(n) as traversal of a tree. All implementations have been provided in Java, JavaScript and Python.


word break

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.

Implementation 1: Children is defined as array
This is the most intuitive implementation. If all words are alphabets a-z, the array size is 26. If there are special characters such as space, the array size is 128. Since it is constant, it wouldn’t affect the complexity. But it takes more memory spaces.

Java

JavaScript

Python

Doodle

autocomplete with trie array doodle

Implementation 2: Children is defined as linked list
The linked list implementations overcome the space problem in Array. The node is created only needed. but it takes time to search the node by char. The same as array size, the longest list size is limited to 26 or 128, based on what characters in the words.

Java

JavaScript

Python

Doodle

autocomplete with trie list doodle

Implementation 3: Children is defined as hash map
This is similar to array implementation. In stead of using char as index, it uses char as key in map. It is preferred by many.

Java

JavaScript

Python

Doodle

autocomplete with trie map doodle

Output:
amazon
amazon prime
amazing
amazing spider man
amazed

O Notation:
Time complexity: O(n), n is number of nodes included (Prefix and branches)
Space complexity: O(n)

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


Download AutocompleteWithTrie.java
Autocomplete with trie (YouTube)
Java Coding Interview Pocket Book (2nd Edition)

Comments are closed