Longest Word With All Prefixes

给一个string组, 求是否有一个string的所有prefix都出现在组里.

Trie找一下

struct TrieNode
{ 
    bool leaf;
    TrieNode *v[128]; 
}; 
TrieNode* newNode(){
    TrieNode* n = new TrieNode;
    for (int i = 0; i < 128; i++)
    {
        n->leaf = false;
        n->v[i] = NULL;
    }
    return n;
}
class Solution {
public:
    void insert (TrieNode* root, string s) {
        TrieNode* cur = root;
        for (auto ch : s){
            if (!cur->v[ch])
                cur->v[ch] = newNode();
            cur = cur->v[ch];      
        }   
        cur->leaf = true; 
    } 
    bool find (TrieNode* root, string s) {
        int count = 0;
        TrieNode* cur = root;
        for (int i = 0; i < s.size() - 1; i++){
           if(cur->v[s[i]]){
               if(cur->v[s[i]]->leaf)
                   count++;
               cur = cur->v[s[i]];
           }
        }   
        return count == s.size() - 1;
    } 
    string longestWord(vector<string>& words) {
        TrieNode* node = newNode();
        for(auto w : words){
            insert(node, w);
        }
        sort(words.begin(), words.end(),[](string a, string b){return a.length() == b.length() ? a < b : b.length() < a.length();});
        for(auto w : words){
            if(find(node, w))
                return w;
        }
        return "";
    } 
};