720.词典中最长的单词 (Medium)*

class TrieNode {
public:
    bool isEnd;
    vector<TrieNode*> next;
    TrieNode() : isEnd(false), next(26, nullptr) {}
};

class Solution {
public:
    string longestWord(vector<string>& words) {
        int n = words.size();
        if(n == 0) {
            return "";
        }
        sort(words.begin(), words.end(), [&](const string& a, const string& b) -> int {
            return (a.length() == b.length() ? a < b : a.length() < b.length());
        });

        auto root = new TrieNode();
        string res;
        for(auto& word : words) {
            auto valid = true;
            auto cur = root;
            int len = word.length();
            for(int i = 0; i < len; i++) {
                if(cur->next[word[i] - 'a'] == nullptr) {
                    cur->next[word[i] - 'a'] = new TrieNode();
                }
                cur = cur->next[word[i] - 'a'];
                if(i < len - 1 && !cur->isEnd) {
                    valid = false;
                    break;
                }
            }
            if(valid) {
                cur->isEnd = true;
                if(len > res.length()) {
                    res = word;
                }
            }
        }
        return res;
    }
};