-
Notifications
You must be signed in to change notification settings - Fork 1
/
Trie.cpp
71 lines (54 loc) · 1.53 KB
/
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
#include <bits/stdc++.h>
using namespace std;
class Trie{
private:
int translate(char c){ return (int) c - 97;}
Trie * found(char c){
for(auto it : tries)
if (it.first == c) return it.second;
return nullptr;
}
public:
bool end_of_word = false;
map<char, Trie *> tries;
Trie() {}
//~Trie(){ for(int i=0; i<tries.size(); i++) if (tries[i]) delete tries[i];}
void insert(string word){
if (word.length() == 1) end_of_word = true;
if (word.empty()) return;
char c = word[0];
word = word.substr(1);
Trie *t = found(c);
if (!t) tries[c] = new Trie();
tries[c]->insert(word);
}
bool search(string word){
char c = word[0];
word = word.substr(1);
Trie *t = found(c);
if(! t) return false;
if(word.empty()) return end_of_word;
return tries[c]->search(word);
}
bool startsWith(string prefix){
char c = prefix[0];
prefix = prefix.substr(1);
Trie *t = found(c);
if(!t) return false;
if(prefix.empty()) return true;
return tries[c]->startsWith(prefix);
}
};
int main(){
Trie t;
t.insert("hello") ;
t.insert("hellos");
cout<<t.search("hell")<<endl;
cout<<t.search("hello")<<endl;
cout<<t.search("hellos")<<endl;
cout<<endl;
cout<<t.startsWith("hell")<<endl;
cout<<t.startsWith("hello")<<endl;
cout<<t.startsWith("hellos")<<endl;
cout<<t.startsWith("e")<<endl;
}