Implement Magic Dictionary LeetCode solution in C++

1
struct node {
2
  bool end = false;
3
  node *children[26];
4
};
5

6
class MagicDictionary {
7
 public:
8
  node *root;
9
  void insert(string &s) {
10
    node *cur = root;
11
    for (char &c : s) {
12
      if (!cur->children[c - 'a']) {
13
        cur->children[c - 'a'] = new node();
14
      }
15
      cur = cur->children[c - 'a'];
16
    }
17
    cur->end = true;
18
  }
19
  MagicDictionary() {
20
    root = new node();
21
  }
22

23
  void buildDict(vector<string> dictionary) {
24
    for (string &s : dictionary) insert(s);
25
  }
26

27
  bool find(int i, string &s, node *cur, int mismatch) {
28
    if (i == s.size() and mismatch == 0) return cur->end;
29
    if (mismatch < 0) return false;
30
    if ((!cur || i == s.size()) and mismatch != 0) return false;
31

32
    int ind = s[i] - 'a';
33
    bool ans = false;
34
    for (int j = 0; j < 26; j++) {
35
      if (cur->children[j]) {
36
        if (j != ind) {
37
          ans |= find(i + 1, s, cur->children[j], mismatch - 1);
38
        } else {
39
          ans |= find(i + 1, s, cur->children[j], mismatch);
40
        }
41
      }
42
    }
43
    return ans;
44
  }
45
  bool search(string searchWord) {
46
    return find(0, searchWord, root, 1);
47
  }
48
};