leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0676.cpp (1718B)

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 };