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.
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
|
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 |
import java.util.*; public class AutocompleteTrieArray { //don't use 26 if there is space or any other special characters static final int NUM_OF_CHARS = 128 ; static class TrieNode { char data; TrieNode[] children = new TrieNode[NUM_OF_CHARS]; boolean isEnd = false; //Constructor, Time O(1), Space O(1), 128 is constant TrieNode(char c) { data = c; } } static class Trie { TrieNode root = new TrieNode(' ') ; //Inserts a word into the trie, Iteration //Time O(s), Space O(s), s is word length void insert(String word) { TrieNode node = root; for (char ch: word.toCharArray()) { if (node.children[ch] == null) node.children[ch] = new TrieNode(ch); node = node.children[ch]; } node.isEnd = true; } //find the node with prefix's last char, then call helper to find all words using recursion //Time O(n), Space O(n), n is number of nodes included(prefix and branches) List<String> autocomplete(String prefix) { TrieNode node = root; List<String> res = new ArrayList<String>(); for (char ch: prefix.toCharArray()) { node = node.children[ch]; if (node == null) return new ArrayList<String>(); } helper(node, res, prefix.substring(0, prefix.length()-1)); return res; } //recursion function called by autocomplete //Time O(n), Space O(n), n is number of nodes in branches void helper(TrieNode node, List<String> res, String prefix) { if (node == null ) //base condition return; if (node.isEnd) res.add(prefix + node.data); for (TrieNode child: node.children) helper(child, res, prefix + node.data); } } 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("apple"); System.out.println(t.autocomplete("amaz")); } } |
JavaScript
|
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 |
class TrieNode { //Constructor, Time O(1), Space O(1) constructor(c) { this.data = c; this.children = {}; //array this.isEnd = false; } } class Trie { //Constructor, Time O(1), Space O(1) constructor() { this.root = new TrieNode(''); } //insert a word into the trie, iteration //Time O(s), Space O(s), s is word length insert(word) { let node = this.root; for (let ch of word) { if (node.children[ch]== null) node.children[ch] = new TrieNode(ch); node = node.children[ch]; } node.isEnd = true; } //returns all words with given prefix, call recursion function //Time O(n), Space O(n), n is number of nodes included(prefix and branches) autocomplete(prefix) { var node = this.root; var res = []; for (let ch of prefix) { node = node.children[ch]; if (node == null) return res; } this.helper(node, res, prefix.substring(0, prefix.length-1)); return res; } //recursive function called by autocomplete //Time O(n), Space O(n), n is number of nodes in branches helper(node, res, prefix) { if (node.isEnd) res.push(prefix + node.data); for (let child in node.children) //array this.helper(node.children[child], res, prefix + node.data); } } const t = new Trie(); t.insert("amazon"); t.insert("amazon prime"); t.insert("amazing"); t.insert("amazing spider man"); t.insert("amazed"); t.insert("ebay"); a = t.autocomplete("amaz"); console.log(a); |
Python
|
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 |
class TrieNode: #Constructor, Time O(1), Space O(1), 128 is constant def __init__(self, c): self.children = [None]*128 #don't use 26 if there is space or other special characters self.isEnd = False self.data = c class Trie: #Constructor, Time O(1), Space O(1) def __init__(self): self.root = TrieNode('') #inserts a word into the trie, Iteration, #Time O(s), Space O(s), s is word length def insert(self, word): node = self.root for ch in word: idx = ord(ch) if not node.children[idx]: node.children[idx] = TrieNode(ch) node = node.children[idx] node.isEnd = True #returns all words with given prefix #Time O(n), Space O(n), n is number of nodes included(prefix and branches) def autocomplete(self, prefix): node = self.root res = [] for ch in prefix: node = node.children[ord(ch)] if node == None: return [] self.helper(node, res, prefix[:-1]) return res #recursion function called by autocomplete, Time O(n), Space O(n) # n is number of nodes in bra def helper(self, node, res, prefix): if node == None: return if node.isEnd : res.append(prefix + node.data) for child in node.children: self.helper(child, res,prefix + node.data) t = Trie() t.insert("amazon") t.insert("amazon prime") t.insert("amazing") t.insert("amazing spider man") t.insert("amazed") t.insert("apple") print(t.autocomplete('amaz')) |
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
|
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 |
import java.util.*; public class AutocompleteTrieList { static class TrieNode { char data; LinkedList<TrieNode> children = new LinkedList<>(); boolean isEnd = false; //Constructor, Time O(1), Space O(1) TrieNode(char c) { data = c; } //find the node by char, the same functionality as children[ch] in array implementation //Time O(k), Space O(1), k is number of children of this node TrieNode getChild(char c) { if (children != null) for (TrieNode child : children) if (child.data == c) return child; return null; } } static class Trie { TrieNode root = new TrieNode(' '); //Add a word to trie, Iteration, Time O(s), Space O(s), s is word length void insert(String word) { TrieNode node = root; for (char ch : word.toCharArray()) { if (node.getChild(ch) == null) node.children.add(new TrieNode(ch)); node = node.getChild(ch); } node.isEnd = true; } //find the node with prefix's last char, then call helper to find all words using recursion //Recursion, Time O(n), Space O(n), n is number of nodes involved (include prefix and branches) List<String> autocomplete(String prefix) { TrieNode node = root; List<String> res = new ArrayList<String>(); for (char ch: prefix.toCharArray()) { //find end of prefix node = node.getChild(ch); if (node == null) return new ArrayList<String>(); } helper(node, res, prefix.substring(0, prefix.length()-1)); return res; } //recursion helper, Time O(n), Space O(n), n is number of nodes in branches void helper(TrieNode node, List<String> res, String prefix) { if (node.isEnd) res.add(prefix + node.data); for (TrieNode child : node.children) helper(child, res, prefix + node.data); } } 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("apple"); System.out.println(t.autocomplete("amaz")); } } |
JavaScript
|
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 |
class TrieNode { //Constructor, Time O(1), Space O(1) constructor(c) { this.data = c; this.children = new Array(); //List this.isEnd = false; } //find the node by char, the same functionality as children[ch] in array implementation //Time O(k), Space O(1), k is number of children of this node getChild(c) { if (this.children != null) for (let child of this.children) if (child.data == c) return child; return null; } } class Trie { //Constructor, Time O(1), Space O(1) constructor() { this.root = new TrieNode(''); } //insert a word into the trie, Time O(s), Space O(s), s is word length insert (word) { var node = this.root; for (let ch of word) { if (node.getChild(ch) == null) node.children.push(new TrieNode(ch)); node = node.getChild(ch); } node.isEnd = true; } //find all word with given prefix, call recursion function //Time O(n), Space O(n), n is number of nodes involved (include prefix and branches) autocomplete (prefix) { var node = this.root; var res = new Array(); for (let ch of prefix) { //find end of prefix node = node.getChild(ch); if (node == null) return new Array(); } this.helper(node, res, prefix.substring(0, prefix.length-1)); return res; } //recursive function called by autocomplete //Time O(n), Space O(n), n is number of nodes in branches helper (node, res, prefix) { if (node.isEnd) res.push(prefix + node.data); for (let child of node.children) //list this.helper(child, res, prefix + node.data); } } const t = new Trie(); t.insert("amazon"); t.insert("amazon prime"); t.insert("amazing"); t.insert("amazing spider man"); t.insert("amazed"); t.insert("apple"); a = t.autocomplete("amaz"); console.log(a); |
Python
|
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 |
class TrieNode: #Constructor, Time O(1), Space O(1) def __init__(self, c): self.data = c self.children = [] # list self.isEnd = False #find the node by char, the same functionality as children[ch] in array implementation #Time O(k), Space O(1), k is number of children of this node def getChild(self, c): if self.children != None: for child in self.children: if child.data == c: return child return None class Trie: #Constructor, Time O(1), Space O(1) def __init__(self): self.root = TrieNode('') #Add a word to trie, Iteration, Time O(s), Space O(s), s is word length def insert(self, word) : node = self.root for ch in word: if node.getChild(ch) == None: node.children.append(TrieNode(ch)) node = node.getChild(ch) node.isEnd = True #find all word with given prefix #Time O(n), Space O(n), n is number of nodes involved (include prefix and branches) def autocomplete(self, prefix): node = self.root res = [] for char in prefix : node = node.getChild(char) if node == None: return [] self.helper(node, res, prefix[:-1]) return res #recursive function called by autocomplete #Time O(n), Space O(n), n is number of nodes in branches def helper(self, node, res, prefix) : if node.isEnd: res.append(prefix + node.data); for child in node.children: self.helper(child, res, prefix + node.data) t = Trie() t.insert("amazon") t.insert("amazon prime") t.insert("amazing") t.insert("amazing spider man") t.insert("amazed") t.insert("apple") print(t.autocomplete('amaz')) |
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
|
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 |
import java.util.*; public class AutocompleteTrieMap { static class TrieNode { char data; HashMap<Character, TrieNode> children = new HashMap<>(); boolean isEnd = false; //Constructor, Time O(1), Space O(1) TrieNode(char c) { this.data = c; } } static class Trie { TrieNode root = new TrieNode(' '); //Add a word to trie, Iteration, Time O(s), Space O(s), s is word length void insert(String word) { TrieNode node = root; for (char ch : word.toCharArray()) { if (!node.children.containsKey(ch)) node.children.put(ch, new TrieNode(ch)); node = node.children.get(ch); } node.isEnd = true; } //find all word with given prefix //Time O(n), Space O(n), n is number of nodes involved (include prefix and branches) List<String> autocomplete(String prefix) { List<String> res = new LinkedList<String>(); TrieNode node = root; for (char ch : prefix.toCharArray()) { if (node.children.containsKey(ch)) node = node.children.get(ch); else return res; } helper(node, res, prefix.substring(0, prefix.length()-1)); return res; } // recursive function called by autocomplete //Time O(n), Space O(n), n is number of nodes in branches void helper(TrieNode node, List<String> res, String prefix) { if (node.isEnd) res.add(prefix + node.data); for (Character ch : node.children.keySet()) helper(node.children.get(ch), res, prefix + node.data); } } 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("apple"); System.out.println(t.autocomplete("amaz")); } } |
JavaScript
|
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 |
class TrieNode { //Constructor, Time O(1), Space O(1) constructor(c) { this.data = c; this.isEnd = false; this.children = new Map(); //map } } class Trie { //Constructor, Time O(1), Space O(1) constructor() { this.root = new TrieNode(''); } //inserts a word into the trie. Time O(s), Space O(s), s is word length insert (word) { var node = this.root; for (let ch of word) { if (!node.children.has(ch)) node.children.set(ch, new TrieNode(ch)); node = node.children.get(ch); } node.isEnd = true; } //find all word with given prefix, call recursion function //Time O(n), Space O(n), n is number of nodes involved (include prefix and branches) autocomplete (word) { var res = new Array(); var node = this.root; for (let ch of word) { if (node.children.has(ch)) node = node.children.get(ch); else return res; } this.helper(node, res, word.substring(0, word.length-1)); return res; } //recursive function called by autocomplete //Time O(n), Space O(n), n is number of nodes in branches helper (node, res, prefix) { if (node.isEnd) res.push(prefix + node.data); for (let c of node.children.keys()) this.helper(node.children.get(c), res, prefix + node.data); } } const t = new Trie(); t.insert("amazon"); t.insert("amazon prime"); t.insert("amazing"); t.insert("amazing spider man"); t.insert("amazed"); t.insert("ebay"); t.insert("apple"); a = t.autocomplete("amaz"); console.log(a); |
Python
|
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 |
class TrieNode: #constructor, Time O(1) Space O(1) def __init__(self, c): self.data = c self.isEnd = False self.children = {} #map class Trie: #constructor, Time O(1) Space O(1) def __init__(self): self.root = TrieNode('') #Add a word to trie, Time O(s) Space O(1) s is word length def insert(self, word): node = self.root for ch in word: if not ch in node.children: node.children[ch] = TrieNode(ch) node = node.children[ch] node.isEnd = True #find all word with given prefix #Time O(n), Space O(n), n is number of nodes involved (include prefix and branches) def autocomplete(self, word): res = [] node = self.root for ch in word: if ch in node.children: node = node.children[ch] else: return [] self.helper(node, res, word[:-1]) #except the last "ama", node is "z" return res #recursive function called by autocomplete #Time O(n), Space O(n), n is number of nodes in branches def helper(self, node, res, prefix): if node.isEnd: res.append(prefix + node.data) for child in node.children.values(): self.helper(child, res, prefix + node.data) t = Trie() t.insert("amazon") t.insert("amazon prime") t.insert("amazing") t.insert("amazing spider man") t.insert("amazed") t.insert("apple") a = t.autocomplete("amaz") print(a) |
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
Trie (part 1) – array implementation
Trie (part 2) – linked list implementation
Trie (part 3) – hash map implementation
Autocomplete with trie (YouTube)
Java Coding Interview Pocket Book (2nd Edition)
