-
Notifications
You must be signed in to change notification settings - Fork 0
/
211-Design Add and Search Words Data Structure.cpp
83 lines (72 loc) · 2.3 KB
/
211-Design Add and Search Words Data Structure.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
class TrieNode {
public:
bool word;
TrieNode* next[26]{};
TrieNode(): word(false) {}
};
class WordDictionary {
public:
/** Initialize your data structure here. */
WordDictionary(): root(new TrieNode) {}
/** Adds a word into the data structure. */
void addWord(string word) {
TrieNode* node = root;
for(char c : word) {
if(!node->next[c-'a'])
node->next[c-'a'] = new TrieNode();
node = node->next[c-'a'];
}
node->word = true;
}
/** 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) {
return search(word, 0, root);
}
private:
TrieNode* root;
bool search(const string& word, int pos, TrieNode* node) {
if(pos == word.size()) return node->word;
if(word[pos] != '.') {
TrieNode* tmp = node->next[word[pos]-'a'];
return tmp ? search(word, pos+1, tmp) : false;
} else {
for(int j = 0; j < 26; ++j) {
TrieNode* tmp = node->next[j];
if(tmp && search(word, pos+1, tmp))
return true;
}
}
return false;
}
};
// class WordDictionary {
// public:
// /** Initialize your data structure here. */
// WordDictionary() {}
// /** Adds a word into the data structure. */
// void addWord(string word) {
// words[word.size()].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) {
// for(auto s : words[word.size()])
// if(isEqual(word, s))
// return true;
// return false;
// }
// bool isEqual(string a, string b) {
// for(int i = 0; i < a.size(); ++i){
// if(a[i] == '.') continue;
// if(a[i] != b[i]) return false;
// }
// return true;
// }
// private:
// unordered_map<int, vector<string>> words;
// };
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary* obj = new WordDictionary();
* obj->addWord(word);
* bool param_2 = obj->search(word);
*/