0720.cpp (1270B)
1 class Solution { 2 struct Node { 3 Node *children[26] = {0}; 4 bool term = false; 5 6 void insert(const string &s) { 7 Node *crnt = this; 8 for (int i = 0; i < size(s); i++) { 9 const int idx = s[i] - 'a'; 10 if (!crnt->children[idx]) crnt->children[idx] = new Node(); 11 crnt = crnt->children[idx]; 12 } 13 crnt->term = true; 14 } 15 16 bool check(const string &s) const { 17 const Node *crnt = this; 18 for (int i = 0; i < size(s); i++) { 19 const int idx = s[i] - 'a'; 20 if (!crnt->children[idx]) return false; 21 crnt = crnt->children[idx]; 22 if (!crnt->term) return false; 23 } 24 return true; 25 } 26 }; 27 28 public: 29 string longestWord(const vector<string> &words) const { 30 Node trie; 31 string res; 32 33 for (const auto &word : words) 34 trie.insert(word); 35 for (const auto &word : words) { 36 if (!trie.check(word)) continue; 37 if (size(word) > size(res)) 38 res = word; 39 else if (size(word) == size(res)) 40 res = min(res, word); 41 } 42 43 return res; 44 } 45 };