[C++] Trie
Steps:\n Insert all the strings in the vector in a trie.\n Start checking the strings one by one.\n For the string to be a valid answer, all the prefixes of the
**Steps:**\n* Insert all the strings in the vector in a trie.\n* Start checking the strings one by one.\n* For the string to be a valid answer, all the prefixes of the word should be present in the trie as a word, i.e the boolean variable we use to mark the end of the word should be marked true in the trie.\n* So we traverse word and check if any one of the nodes has the word end variable marked as false, if so then the word is not a valid ans\n* If the string is valid we check if the length of the length of the word is greater than the existing answer, if yes then update, if the length is same as existing answer then we choose the lexicographically smaller between them\n\n```\nclass Solution {\nprivate: \n    struct Node{\n        Node* arr[26];\n        bool end = false;\n    };\npublic:\n    Node* root = new Node();\n    void trie_insert(string &word){\n        Node* node = root;\n        for(int i = 0; i < word.size(); i++){\n            if(node->arr[word[i] - \'a\'] == NULL){\n                node->arr[word[i] - \'a\'] = new Node();\n            }\n            node = node->arr[word[i] - \'a\'];\n        }\n        node->end = true;\n    }\n    bool isValid(string &word, Node* curr){\n        for(int i = 0; i < word.size(); i++){\n            curr = curr->arr[word[i] - \'a\'];\n            if(!curr->end) return false;\n        }\n        return true;\n    }\n    string longestWord(vector<string>& words) {\n        string ans = "";\n        for(auto w: words){\n            trie_insert(w);\n        }    \n        for(int i = words.size() - 1; i >= 0; i--){\n            if(isValid(words[i], root)){\n                if(words[i].length() > ans.length()){\n                    ans = words[i];\n                }else if(words[i].length() == ans.length()){\n                    ans = min(words[i], ans);\n                }\n            }\n        }\n        return ans;\n    }\n};
['Trie', 'C']