Introduction to Tries
A Trie or Prefix Tree an efficient data lookup structure - often used to store large collections of words or dictionaries. With a Trie, search complexities can be reduced to O(k) where k is the key or word length. The autocorrect on your iOS or Android keyboard uses a Trie of the most commonly used words along with fuzzy match algorithms to autocorrect and autosuggest words as you type. You're given a completed
Note:
In the above example, underlined letters represent word boundaries. Word boundaries are important when differentiating between words and prefixes. For example,
TrieNode class that represents one node of a Trie, and a partially complete Trie class. Your task is to complete the insertWord, searchWord and searchPrefix methods on the Trie class. Take a look at the examples below to see what each of these do. Example:
trie.inserWord("AB")
trie.inserWord("ABS")
trie.inserWord("ADS")
trie.inserWord("ADSD")
trie.inserWord("ACS")
Internal Trie Structure:
A
/ | \
B C D
| | |
S S S
|
D
Note:
In the above example, underlined letters represent word boundaries. Word boundaries are important when differentiating between words and prefixes. For example,
searchPrefix("AC") should return true, but since C is not a word boundary, searchWord("AC") should return false. The TrieNode class has a Boolean - isLeaf that is used to denote if the node is a word boundary.
Need a hand? Try out these hints, one at a time.
searchPrefix and searchWord have near identical implementations. The only difference between them is an additional check in searchWord that checks if the last node has its isLeaf set to true or not. If isLeaf != true - searchWord should return false whereas searchPrefix should return true.
When implementing
insertWord, be sure to account for null and "". Inserting them should not modify your Trie's structure. When you're at the last character of the word to be inserted, be sure to set that TrieNode's isLeaf property to true.
Implementing insertWord:
1) Return if
2) Create
3) Get the children of the root :
4) In a for loop, iterate over the characters of the input word. If a child node that corresponds to the current character does not exist, create the node and add it to
5) Within the loop, check for the word boundary and update
Implementing searchPrefix:
This will have a very similar overall structure to
Implementing searchWord:
Similar to
1) Return if
word is null or empty.2) Create
TrieNode cur = root; to iterate over the Trie3) Get the children of the root :
HashMap children = cur.children;4) In a for loop, iterate over the characters of the input word. If a child node that corresponds to the current character does not exist, create the node and add it to
children. If it already exists, simply update children to the children of that node : char c = word.charAt(i);
if (children.containsKey(c)) {
cur = children.get(c);
} else {
TrieNode n = new TrieNode(c);
children.put(c, n);
cur = n;
}
5) Within the loop, check for the word boundary and update
isLeaf accordingly : if (i == word.length() - 1) {
cur.isLeaf = true;
}Implementing searchPrefix:
This will have a very similar overall structure to
insertWord. Instead of creating and inserting nodes, simply check for their presence and update the current node. If at any point an expected node is not found, return false :char c = word.charAt(i);
if (children.containsKey(c)) {
cur = children.get(c);
children = cur.children;
} else {
return false;
}
Implementing searchWord:
Similar to
searchPrefix with an added check for cur.isLeaf 
class TrieNode {
Character c;
Boolean isLeaf = false;
HashMap<Character, TrieNode> children = new HashMap<>();
public TrieNode() {}
public TrieNode(Character c) {
this.c = c;
}
}
class Trie {
private TrieNode root;
// Implement these methods :
public Trie() {}
public void insertWord(String word) {}
public Boolean searchWord(String word) {}
public Boolean searchPrefix(String word) {}
}
This Coding Interview Question is available with an answer in the following programming languages :
C
Java
Python