-
Notifications
You must be signed in to change notification settings - Fork 33
/
trie.h
92 lines (80 loc) · 2.11 KB
/
trie.h
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
/*
* Trie data structure using STL
*
* Author : Vivek Narayanan
*/
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <set>
using namespace std;
class Trie {
public:
map<char, Trie> children;
string value;
bool flag;
Trie(const string &);
void add(char);
string find(const string &);
void insert(const string &);
vector<string> all_prefixes();
vector<string> autocomplete(const string &);
};
Trie::Trie(const string &val="") {
value = val;
flag = false;
}
void Trie::add(char c) {
if (value == "")
children[c] = Trie(string(1, c));
else
children[c] = Trie(value + c);
}
string Trie::find(const string &word) {
Trie * node = this;
for (int i = 0; i < word.length(); i++) {
const char c = word[i];
if (node->children.find(c) == node->children.end())
return "";
else
node = &node->children[c];
}
return node->value;
}
void Trie::insert(const string &word) {
Trie * node = this;
for (int i = 0; i < word.length(); i++) {
const char c = word[i];
if (node->children.find(c) == node->children.end())
node->add(c);
node = &node->children[c];
}
node->flag = true;
}
vector<string> Trie::all_prefixes() {
vector<string> results;
if (flag)
results.push_back(value);
if (children.size()) {
map<char, Trie>::iterator iter;
vector<string>::iterator node;
for(iter = children.begin(); iter != children.end(); iter++) {
vector<string> nodes = iter->second.all_prefixes();
results.insert(results.end(), nodes.begin(), nodes.end());
}
}
return results;
}
vector<string> Trie::autocomplete(const string &prefix) {
Trie * node = this;
vector<string> results;
for (int i = 0; i < prefix.length(); i++) {
const char c = prefix[i];
if (node->children.find(c) == node->children.end())
return results;
else
node = &node->children[c];
}
return node->all_prefixes();
}