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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
import java.util.LinkedList; import java.util.List; import java.util.ArrayList; class TrieNode { char data; LinkedList children; TrieNode parent; boolean isEnd; public TrieNode(char c) { data = c; children = new LinkedList(); isEnd = false; } public TrieNode getChild(char c) { if (children != null) for (TrieNode eachChild : children) if (eachChild.data == c) return eachChild; return null; } //helper of DFS, find all strings with same prefix (starting from the same node) protected List getWords() { List list = new ArrayList(); if (isEnd) { list.add(toString()); } if (children != null) { for (int i=0; i< children.size(); i++) { if (children.get(i) != null) { list.addAll(children.get(i).getWords()); } } } return list; } public String toString() { if (parent == null) { return ""; } else { return parent.toString() + new String(new char[] {data}); } } } class Trie { private TrieNode root; public Trie() { root = new TrieNode(' '); } public void insert(String word) { if (search(word) == true) return; TrieNode current = root; TrieNode pre ; for (char ch : word.toCharArray()) { pre = current; TrieNode child = current.getChild(ch); if (child != null) { current = child; child.parent = pre; } else { current.children.add(new TrieNode(ch)); current = current.getChild(ch); current.parent = pre; } } current.isEnd = true; } public boolean search(String word) { TrieNode current = root; for (char ch : word.toCharArray()) { if (current.getChild(ch) == null) return false; else { current = current.getChild(ch); } } if (current.isEnd == true) { return true; } return false; } //autocomplete public List autocomplete(String prefix) { TrieNode lastNode = root; //find last node of prefix for (int i = 0; i< prefix.length(); i++) { lastNode = lastNode.getChild(prefix.charAt(i)); if (lastNode == null) return new ArrayList(); } //call helper return lastNode.getWords(); } } public class AutocompleteWithTrie { public static void main(String[] args) { Trie t = new Trie(); t.insert("amazon"); t.insert("amazon prime"); t.insert("amazing"); t.insert("amazing spider man"); t.insert("amazed"); t.insert("alibaba"); t.insert("ali express"); t.insert("ebay"); t.insert("walmart"); List a= t.autocomplete("amaz"); for (int i = 0; i < a.size(); i++) { System.out.println(a.get(i)); } } } |
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!
Download AutocompleteWithTrie.java
Autocomplete with trie (YouTube)
Java Coding Interview Pocket Book (2nd Edition)
