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
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.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
.
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.
word
is null or empty.TrieNode cur = root;
to iterate over the TrieHashMap children = cur.children;
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;
}
isLeaf
accordingly : if (i == word.length() - 1) {
cur.isLeaf = true;
}
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;
}
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) {} }
C
Java
Python