forked from jainaman224/Algo_Ds_Notes
-
Notifications
You must be signed in to change notification settings - Fork 1
/
TrieUse.java
131 lines (106 loc) · 2.11 KB
/
TrieUse.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
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
125
126
127
128
129
130
131
import java.util.HashMap;
class TrieNode {
char value;
boolean isTerminal;
HashMap<Character, TrieNode> children ;
public TrieNode(char value) {
this.value = value;
children = new HashMap<>();
}
}
class Trie {
TrieNode root;
int count = 0;
public Trie()
{
root = new TrieNode('\0');
}
public void add(String word)
{
add(root, word);
}
private void add(TrieNode root, String word)
{
if(word.length() == 0)
{
if(root.isTerminal)
return;
root.isTerminal = true;
count++;
return;
}
TrieNode child = root.children.get(word.charAt(0));
if(child == null)
{
child = new TrieNode(word.charAt(0));
root.children.put(word.charAt(0), child);
}
add(child, word.substring(1));
}
public boolean findWord(String word)
{
TrieNode currentNode = root;
for(int i = 0; i < word.length(); i++){
TrieNode child = currentNode.children.get(word.charAt(i));
if(child == null){
return false;
}
currentNode = child;
}
return currentNode.isTerminal;
}
public void remove(String word)
{
remove(root, word);
}
private void remove(TrieNode root, String word)
{
if(word.length() == 0)
{
if(!root.isTerminal)
return;
root.isTerminal = false;
count--;
return;
}
TrieNode child = root.children.get(word.charAt(0));
if(child == null)
return;
remove(child, word.substring(1));
if(child.children.isEmpty() && !child.isTerminal)
{
root.children.remove(child);
}
}
}
class TrieUse{
//Driver Funtion
public static void main(String args[])
{
Trie trie = new Trie();
trie.add("ayushi");
trie.add("aman");
trie.add("adish");
trie.add("swati");
trie.add("ayesha");
trie.add("ayu");
System.out.println(trie.findWord("ayushi"));
System.out.println(trie.findWord("ayush"));
System.out.println(trie.findWord("swati"));
trie.remove("swati");
trie.remove("ayushi");
System.out.println(trie.findWord("ayushi"));
System.out.println(trie.findWord("swati"));
System.out.println(trie.findWord("ayu"));
System.out.println(trie.findWord("ayush"));
/* OUTPUT
true
false
true
false
false
true
false
*/
}
}