diff options
Diffstat (limited to 'add_search_words_data.c')
-rw-r--r-- | add_search_words_data.c | 69 |
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); +} |