0676.cpp (1718B)
1 class MagicDictionary { 2 struct Node { 3 Node(){}; 4 Node *children[27] = {nullptr}; 5 bool &terminate = reinterpret_cast<bool &>(children[0]); 6 }; 7 8 Node *trie = new Node(); 9 10 public: 11 void buildDict(const vector<string> &dictionary) { 12 // create trie and fill it with words 13 for (const auto &word : dictionary) { 14 Node *crnt = trie; 15 for (const char c : word) { 16 const int idx = c & 0x1F; 17 if (!crnt->children[idx]) crnt->children[idx] = new Node(); 18 crnt = crnt->children[idx]; 19 } 20 crnt->terminate = true; 21 } 22 } 23 24 bool search(const string &searchWord) { 25 typedef pair<const Node *, int> entry; 26 stack<entry> st; 27 28 const int n = size(searchWord); 29 30 // generate all posible char changes that make sense 31 const Node *crnt = trie; 32 for (int i = 0; i < n; i++) { 33 const int idx = searchWord[i] & 0x1F; 34 for (int j = 1; j <= 26; j++) { 35 if (j == idx) continue; 36 if (crnt->children[j]) st.emplace(crnt->children[j], i + 1); 37 } 38 if (!crnt->children[idx]) break; 39 crnt = crnt->children[idx]; 40 } 41 42 // check are any of them valid 43 while (!st.empty()) { 44 auto [crnt, start] = st.top(); 45 st.pop(); 46 for (int i = start; i < n; i++) { 47 const int idx = searchWord[i] & 0x1F; 48 if (!crnt->children[idx]) goto next; 49 crnt = crnt->children[idx]; 50 } 51 if (crnt->terminate) return true; 52 next:; 53 } 54 return false; 55 } 56 };