leetcode

Solution to some Leetcode problems written in C++

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

0720.cpp (1270B)

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