0208.cpp (936B)
1 class Trie { 2 struct Record { 3 bool end; 4 array<Record *, 26> records = {nullptr}; 5 6 Record *insert(int x) { 7 if (records[x]) return records[x]; 8 return records[x] = new Record(); 9 } 10 11 Record *check(int x) { return records[x]; } 12 }; 13 14 Record *record = new Record; 15 Record *last(string word) { 16 Record *crnt = record; 17 for (char c : word) 18 if (!crnt) 19 return nullptr; 20 else 21 crnt = crnt->check(c - 'a'); 22 return crnt; 23 } 24 25 public: 26 void insert(string word) { 27 Record *crnt = record; 28 for (char c : word) 29 crnt = crnt->insert(c - 'a'); 30 crnt->end = true; 31 } 32 33 bool search(string word) { 34 Record *crnt = last(word); 35 if (!crnt) return false; 36 return crnt->end; 37 } 38 39 bool startsWith(string prefix) { return last(prefix); } 40 };