forked from prateekshyap/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
LC_211_DesignAddSearchWordsDataStructure.cpp
113 lines (101 loc) · 2.58 KB
/
LC_211_DesignAddSearchWordsDataStructure.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
/*
211. Design Add and Search Words Data Structure
https://leetcode.com/problems/design-add-and-search-words-data-structure/
*/
// /*
class WordDictionary {
struct TrieNode{
TrieNode* children[26];
bool isEnd;
};
TrieNode *root;
public:
WordDictionary() {
root = new TrieNode();
}
void addWord(string word) {
TrieNode* ptr = root;
int key=0;
for(char &c: word)
{
key = c-'a';
if(ptr->children[key] == nullptr)
ptr->children[key] = new TrieNode();
ptr = ptr->children[key];
}
ptr->isEnd = true;
}
bool TrieSearch(int i, TrieNode* ptr, string& word)
{
// cout<<i<<" "<<word<<endl;
if(i == word.length()){
return ptr->isEnd;
}
int key=0;
if(word[i] != '.')
{
for(int j=i; j<word.size(); j++)
{
key = word[j]-'a';
if(ptr->children[key] == nullptr)
return false;
else
{
ptr = ptr->children[key];
}
if(j+1<word.size() and word[j+1] == '.')
return TrieSearch(j+1, ptr, word);
}
return ptr->isEnd;
}
else{
for(int j=0; j<26; j++)
{
if(ptr->children[j])
{
if(TrieSearch(i+1, ptr->children[j], word))
return true;
}
}
}
return false;
}
bool search(string word) {
return TrieSearch(0, root, word);
}
};
// */
/* // Approach 2
class WordDictionary {
public:
array<unordered_set<string>, 26> dict;
WordDictionary() {
}
void addWord(string word) {
dict[word.size()].insert(word);
}
bool search(string word) {
if(word.find('.') == string::npos)
return dict[word.size()].count(word);
for(auto& d: dict[word.size()])
{
bool match = true;
for(int i=0; i<word.size(); i++)
{
if(word[i] != '.' and d[i]!=word[i])
{
match=false; break;
}
}
if(match) return true;
}
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);
*/