-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
208.cpp
116 lines (93 loc) · 2.89 KB
/
208.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
__________________________________________________________________________________________________
sample 56 ms submission
static auto _=[](){cin.tie(nullptr);ios::sync_with_stdio(false);return 0;}();
class Trie
{
typedef struct node {
bool word;
node* next[26];
node() : word(false) { memset(next, 0, sizeof(next)); }
} *Node;
Node root;
public:
/** Initialize your data structure here. */
Trie()
{
this->root = new node();
}
/** Inserts a word into the trie. */
void insert(string word)
{
Node current = this->root;
for (auto letter : word)
{
current =
current->next[letter - 'a'] == nullptr ?
current->next[letter - 'a'] = new node() :
current->next[letter - 'a'];
}
current->word = true;
}
/** Returns if the word is in the trie. */
bool search(string word)
{
Node current = this->root;
for (auto letter : word)
{
current = current->next[letter - 'a'];
if (current == nullptr)
return false;
}
return current->word;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix)
{
Node current = this->root;
for (auto letter : prefix)
{
current = current->next[letter - 'a'];
if (current == nullptr)
return false;
}
return current != nullptr;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
__________________________________________________________________________________________________
sample 23976 kb submission
class Trie {
public:
/** Initialize your data structure here. */
Trie() {
}
/** Inserts a word into the trie. */
void insert(string word) {
prefixs += "_"+word+"_";
}
/** Returns if the word is in the trie. */
bool search(string word) {
return(prefixs.find("_"+word+"_")!=string::npos);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
if(prefixs.find("_"+prefix)!=string::npos) { return(true); }
return(false);
}
unordered_set<string> m_set;
string prefixs;
};
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* bool param_2 = obj.search(word);
* bool param_3 = obj.startsWith(prefix);
*/
__________________________________________________________________________________________________