-
Notifications
You must be signed in to change notification settings - Fork 37
/
Implement Trie.cpp
103 lines (99 loc) · 1.96 KB
/
Implement Trie.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
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define MAXN 100001
#define INF 1e18+1
struct Node {
Node *links[26];
bool flag = false;
//checks if the reference trie is present or not
bool containKey(char ch) {
return (links[ch - 'a'] != NULL);
}
//creating reference trie
void put(char ch, Node *node) {
links[ch - 'a'] = node;
}
//to get the next node for traversal
Node *get(char ch) {
return links[ch - 'a'];
}
//setting flag to true at the end of the word
void setEnd() {
flag = true;
}
//checking if the word is completed or not
bool isEnd() {
return flag;
}
};
class Trie {
private:
Node* root;
public:
Trie() {
//creating new obejct
root = new Node();
}
void insert(string word) {
//initializing dummy node pointing to root initially
Node *node = root;
for (int i = 0; i < word.size(); i++) {
if (!node->containKey(word[i])) {
node->put(word[i], new Node());
}
//moves to reference trie
node = node->get(word[i]);
}
node->setEnd();
}
bool search(string word) {
Node *node = root;
for (int i = 0; i < word.size(); i++) {
if (!node->containKey(word[i])) {
return false;
}
node = node->get(word[i]);
}
return node->isEnd();
}
bool startsWith(string prefix) {
Node* node = root;
for (int i = 0; i < prefix.size(); i++) {
if (!node->containKey(prefix[i])) {
return false;
}
node = node->get(prefix[i]);
}
return true;
}
};
int main()
{
int n = 5;
vector<int>type = {1, 1, 2, 3, 2};
vector<string>value = {"hello", "help", "help", "hel", "hel"};
Trie trie;
for (int i = 0; i < n; i++) {
if (type[i] == 1) {
trie.insert(value[i]);
}
else if (type[i] == 2) {
if (trie.search(value[i])) {
cout << "true" << "\n";
}
else {
cout << "false" << "\n";
}
}
else {
if (trie.startsWith(value[i])) {
cout << "true" << "\n";
}
else {
cout << "false" << "\n";
}
}
}
}