aboutsummaryrefslogtreecommitdiff
path: root/add_search_words_data.c
blob: 1661cfb68b96998c093ca3e66a96a68200bb4989 (plain)
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
// 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);
}