-
Notifications
You must be signed in to change notification settings - Fork 77
/
Implement_Trie – II.cpp
164 lines (143 loc) · 4.22 KB
/
Implement_Trie – II.cpp
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
// Problem Statement: Implement a data structure ”TRIE” from scratch. Complete some functions.
// 1) Trie(): Initialize the object of this “TRIE” data structure.
// 2) insert(“WORD”): Insert the string “WORD” into this “TRIE” data structure.
// 3) countWordsEqualTo(“WORD”): Return how many times this “WORD” is present in this “TRIE”.
// 4) countWordsStartingWith(“PREFIX”): Return how many words are there in this “TRIE” that have the string “PREFIX” as a prefix.
// 5) erase(“WORD”): Delete this string “WORD” from the “TRIE”.
// Note:
// 1. If erase(“WORD”) function is called then it is guaranteed that the “WORD” is present in the “TRIE”.
// 2. If you are going to use variables with dynamic memory allocation then you need to release the memory associated with them at the end of your solution.
// Example:
// Input:
// 1
// 6
// insert samsung
// insert samsung
// insert vivo
// erase vivo
// countWordsEqualTo samsung
// countWordsStartingWith vi
// Output:
// 2
// 0
// Explanation:
// Insert “samsung”: we are going to insert the word “samsung” into the “TRIE”.
// Insert “samsung”: we are going to insert the word “samsung” again into the “TRIE”.
// Insert “vivo”: we are going to insert the word “vivo” into the “TRIE”.
// Erase “vivo”: we are going to delete the word “vivo” from the “TRIE”.
// countWordsEqualTo “samsung”: There are two instances of “samsung” is present in “TRIE”.
// countWordsStartWith “vi”:There is not a single word in the “TRIE” that starts from the prefix “vi”.
#include <bits/stdc++.h>
using namespace std;
struct Node {
Node * links[26];
int cntEndWith = 0;
int cntPrefix = 0;
bool containsKey(char ch) {
return (links[ch - 'a'] != NULL);
}
Node * get(char ch) {
return links[ch - 'a'];
}
void put(char ch, Node * node) {
links[ch - 'a'] = node;
}
void increaseEnd() {
cntEndWith++;
}
void increasePrefix() {
cntPrefix++;
}
void deleteEnd() {
cntEndWith--;
}
void reducePrefix() {
cntPrefix--;
}
int getEnd() {
return cntEndWith;
}
int getPrefix() {
return cntPrefix;
}
};
class Trie {
private:
Node * root;
public:
/** Initialize your data structure here. */
Trie() {
root = new Node();
}
/** Inserts a word into the trie. */
void insert(string word) {
Node * node = root;
for (int i = 0; i < word.length(); i++) {
if (!node -> containsKey(word[i])) {
node -> put(word[i], new Node());
}
node = node -> get(word[i]);
node -> increasePrefix();
}
node -> increaseEnd();
}
int countWordsEqualTo(string &word)
{
Node *node = root;
for (int i = 0; i < word.length(); i++)
{
if (node->containsKey(word[i]))
{
node = node->get(word[i]);
}
else
{
return 0;
}
}
return node->getEnd();
}
int countWordsStartingWith(string & word) {
Node * node = root;
for (int i = 0; i < word.length(); i++) {
if (node -> containsKey(word[i])) {
node = node -> get(word[i]);
} else {
return 0;
}
}
return node -> getPrefix();
}
void erase(string & word) {
Node * node = root;
for (int i = 0; i < word.length(); i++) {
if (node -> containsKey(word[i])) {
node = node -> get(word[i]);
node -> reducePrefix();
} else {
return;
}
}
node -> deleteEnd();
}
};
int main() {
Trie T;
T.insert("apple");
T.insert("apple");
T.insert("apps");
T.insert("apps");
string word1 = "apps";
cout<<"Count Words Equal to "<< word1<<" "<<T.countWordsEqualTo(word1)<<endl;
string word2 = "abc";
cout<<"Count Words Equal to "<< word2<<" "<<T.countWordsEqualTo(word2)<<endl;
string word3 = "ap";
cout<<"Count Words Starting With "<<word3<<" "<<T.countWordsStartingWith(word3)
<<endl;
string word4 = "appl";
cout<<"Count Words Starting With "<< word4<<" "<<T.countWordsStartingWith(word4)
<<endl;
T.erase(word1);
cout<<"Count Words equal to "<< word1<<" "<<T.countWordsEqualTo(word1)<<endl;
return 0;
}