aboutsummaryrefslogtreecommitdiff
path: root/add_search_words_data.c
diff options
context:
space:
mode:
Diffstat (limited to 'add_search_words_data.c')
-rw-r--r--add_search_words_data.c69
1 files changed, 69 insertions, 0 deletions
diff --git a/add_search_words_data.c b/add_search_words_data.c
new file mode 100644
index 0000000..1661cfb
--- /dev/null
+++ b/add_search_words_data.c
@@ -0,0 +1,69 @@
+// 211. Design Add and Search Words Data Structure
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/*
+ * design data structure that supports adding new words and finding if a string
+ * matches any previously added string. implement WordDictionary class (rather
+ * self explanatory)
+ */
+
+typedef struct trieNode {
+ struct trieNode *sub_char[26];
+ bool eow;
+} WordDictionary;
+
+WordDictionary *wordDictionaryCreate() {
+ WordDictionary *obj = (WordDictionary *)calloc(1, sizeof(WordDictionary));
+ return obj;
+}
+
+void wordDictionaryAddWord(WordDictionary *obj, char *word) {
+ while (*word) {
+ if (obj->sub_char[*word - 'a'] == NULL)
+ obj->sub_char[*word - 'a'] =
+ (WordDictionary *)calloc(1, sizeof(WordDictionary));
+ obj = obj->sub_char[*word - 'a'];
+ word++;
+ }
+ obj->eow = true;
+}
+
+bool wordDictionarySearch(WordDictionary *obj, char *word) {
+ while (*word) {
+ if (*word == '.') {
+ for (uint8_t i = 0; i < 26; i++) {
+ if (!obj->sub_char[i])
+ continue;
+ bool a = wordDictionarySearch(obj->sub_char[i], word + 1);
+ if (a)
+ return true;
+ }
+ return false;
+ } else if (!obj->sub_char[*word] - 'a')
+ return false;
+ obj = obj->sub_char[*word - 'a'];
+ word++;
+ }
+ if (obj->eow)
+ return true;
+ else
+ return false;
+}
+
+void wordDictionaryFree(WordDictionary *obj) {
+ for (uint8_t i = 0; i < 26; i++)
+ if (!obj->sub_char[i])
+ continue;
+ free(obj);
+}
+
+int main() {
+ WordDictionary *obj = wordDictionaryCreate();
+ wordDictionaryAddWord(obj, "foo");
+ bool param_2 = wordDictionarySearch(obj, "bar");
+ wordDictionaryFree(obj);
+}