leetcode

commit eda9eb59b892f728e009d7c85b1246e308cc0025
parent db83ec26cb04c037bd48bfaa9a824ff56f108183
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 19 Mar 2023 14:37:09 +0100

Daily Problem

Diffstat:
A
Problems/0211.cpp
 | 
32
++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 33 insertions(+), 0 deletions(-)
diff --git a/Problems/0211.cpp b/Problems/0211.cpp
@@ -0,0 +1,32 @@
+class WordDictionary {
+  vector<WordDictionary *> children;
+  bool isEndOfWord = false;
+  ;
+
+public:
+  WordDictionary() : children(vector<WordDictionary *>(26, nullptr)) {}
+
+  void addWord(string word) {
+    WordDictionary *crnt = this;
+    for (char c : word) {
+      if (crnt->children[c - 'a'] == nullptr)
+        crnt->children[c - 'a'] = new WordDictionary();
+      crnt = crnt->children[c - 'a'];
+    }
+    crnt->isEndOfWord = true;
+  }
+
+  bool search(string word) {
+    WordDictionary *crnt = this;
+    for (int i = 0; i < word.length(); ++i) {
+      if (word[i] == '.') {
+        for (auto c : crnt->children)
+          if (c && c->search(word.substr(i + 1))) return true;
+        return false;
+      }
+      if (crnt->children[word[i] - 'a'] == nullptr) return false;
+      crnt = crnt->children[word[i] - 'a'];
+    }
+    return crnt && crnt->isEndOfWord;
+  }
+};
diff --git a/README.md b/README.md
@@ -173,6 +173,7 @@ for solving problems.
 |  0208  |   Medium   | [Implement Trie (Prefix Tree)](Problems/0208.cpp)                                                |
 |  0209  |   Medium   | [Minimum Size Subarray Sum](Problems/0209.cpp)                                                   |
 |  0210  |   Medium   | [Course Schedule II](Problems/0210.cpp)                                                          |
+|  0211  |   Medium   | [Design Add and Search Words Data Structure](Problems/0211.cpp)                                  |
 |  0213  |   Medium   | [House Robber II](Problems/0213.cpp)                                                             |
 |  0215  |   Medium   | [Kth Largest Element in an Array](Problems/0215.cpp)                                                 |
 |  0217  |    Easy    | [Contains Duplicate](Problems/0217.cpp)                                                          |