-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
211.cpp
99 lines (87 loc) · 2.54 KB
/
211.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
__________________________________________________________________________________________________
sample 64 ms submission
void beforeMain(void) __attribute__((constructor));
void beforeMain(void) {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
}
class WordDictionary {
struct trie {
bool end = false;
trie* child[26UL] = {nullptr};
};
trie data;
bool search(const trie* t, const char* w, const char* end) {
for (; w < end; ++w) {
if (*w == '.') {
for (int8_t j = 0; j < 26; ++j) {
if (t->child[j] && search(t->child[j], w + 1, end)) {
return true;
}
}
return false;
}
const int8_t c = *w - 'a';
if (!t->child[c]) {
return false;
}
t = t->child[c];
}
return t->end;
}
public:
inline void addWord(const string& word) {
trie* t = &data;
for (const int8_t& c : word) {
if (!t->child[c - 'a']) {
t->child[c - 'a'] = new trie;
};
t = t->child[c - 'a'];
}
t->end = true;
}
inline bool search (const string& word) {
const char* wData = word.data();
return search(&data, wData, wData + word.size());
}
};
__________________________________________________________________________________________________
sample 31204 kb submission
class WordDictionary {
public:
vector<string> dic;
/** Initialize your data structure here. */
WordDictionary() {
}
/** Adds a word into the data structure. */
void addWord(string word) {
dic.push_back(word);
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
bool search(string word) {
auto it = dic.begin();
int i;
int n = word.length();
while(it != dic.end()) {
if ( n == it->length()) {
for (i = 0; i < n; i++) {
if (word[i] == '.')
continue;
if (word[i] != (*it)[i])
break;
}
if (i == n)
return true;
}
it++;
}
return false;
}
};
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* bool param_2 = obj.search(word);
*/
__________________________________________________________________________________________________