Design Add and Search Words Data Structure LeetCode solution in C++

1
class WordDictionary {
2
 public:
3
  struct tr {
4
    bool isword;
5
    vector<tr *> next;
6
    tr() {
7
      next.resize(26, NULL);
8
      isword = false;
9
    }
10
  };
11

12
  tr *root;
13
  WordDictionary() {
14
    root = new tr();
15
  }
16

17
  void addWord(string word) {
18
    tr *cur = root;
19

20
    for (auto c : word) {
21
      if (cur->next[c - 'a'] == NULL) {
22
        cur->next[c - 'a'] = new tr();
23
      }
24
      cur = cur->next[c - 'a'];
25
    }
26

27
    cur->isword = true;
28
  }
29

30
  bool dfs(string &word, int i, tr *cur) {
31
    if (!cur) {
32
      return false;
33
    }
34

35
    if (i == word.size()) {
36
      return cur->isword;
37
    }
38

39
    for (; i < word.size(); i++) {
40
      char c = word[i];
41
      if (c == '.') {
42
        for (auto it : cur->next) {
43
          if (dfs(word, i + 1, it)) {
44
            return true;
45
          }
46
        }
47
        return false;
48
      } else {
49
        if (cur->next[c - 'a'] == NULL) {
50
          return false;
51
        }
52
        cur = cur->next[c - 'a'];
53
      }
54
    }
55

56
    return cur->isword;
57
  }
58

59
  bool search(string word) {
60
    return dfs(word, 0, root);
61
  }
62
};
63

64
/**
65
 * Your WordDictionary object will be instantiated and called as such:
66
 * WordDictionary* obj = new WordDictionary();
67
 * obj->addWord(word);
68
 * bool param_2 = obj->search(word);
69
 */