leetcode

0 class MagicDictionary {

1 struct Node {

2 Node(){};

3 Node *children[27] = {nullptr};

4 bool &terminate = reinterpret_cast<bool &>(children[0]);

5 };

6

7 Node *trie = new Node();

8

9 public:

10 void buildDict(const vector<string> &dictionary) {

11 // create trie and fill it with words

12 for (const auto &word : dictionary) {

13 Node *crnt = trie;

14 for (const char c : word) {

15 const int idx = c & 0x1F;

16 if (!crnt->children[idx]) crnt->children[idx] = new Node();

17 crnt = crnt->children[idx];

18 }

19 crnt->terminate = true;

20 }

21 }

22

23 bool search(const string &searchWord) {

24 typedef pair<const Node *, int> entry;

25 stack<entry> st;

26

27 const int n = size(searchWord);

28

29 // generate all posible char changes that make sense

30 const Node *crnt = trie;

31 for (int i = 0; i < n; i++) {

32 const int idx = searchWord[i] & 0x1F;

33 for (int j = 1; j <= 26; j++) {

34 if (j == idx) continue;

35 if (crnt->children[j]) st.emplace(crnt->children[j], i + 1);

36 }

37 if (!crnt->children[idx]) break;

38 crnt = crnt->children[idx];

39 }

40

41 // check are any of them valid

42 while (!st.empty()) {

43 auto [crnt, start] = st.top();

44 st.pop();

45 for (int i = start; i < n; i++) {

46 const int idx = searchWord[i] & 0x1F;

47 if (!crnt->children[idx]) goto next;

48 crnt = crnt->children[idx];

49 }

50 if (crnt->terminate) return true;

51 next:;

52 }

53 return false;

54 }

55 };