leetcode

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