PROBLEM DESCRIPTION
Trie is an efficient information retrieval data structure. This data structure is used to store Strings and search strings, String stored can also be deleted. Given a Trie root for a larger string super and a string key, delete all the occurences of key in the Trie.
SOLUTION
To solve this, we traverse through the Trie using the characters from the given key, one by one. For each character, we check if there’s a corresponding child node using the subNode method. Once we reach the last character of the key, we mark the isEnd property of the final node as false, indicating that the word is no longer considered a valid entry in the Trie.
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
/*
class TrieNode
{
char content;
boolean isEnd;
int count;
LinkedList<TrieNode> childList;
public TrieNode(char c)
{
childList = new LinkedList<TrieNode>();
isEnd = false;
content = c;
count = 0;
}
public TrieNode subNode(char c)
{
if (childList != null)
for (TrieNode eachChild : childList)
if (eachChild.content == c)
return eachChild;
return null;
}
}*/
class Solution
{
public static void deleteKey(TrieNode root, char[] key)
{
for(int i=0; i<key.length; i++){
char ch = key[i];
root = root.subNode(ch);
}
root.isEnd = false;
}
}