Unleash the Ultimate Word: Building the Longest Word with Power-Packed Prefixes Using a Trie!
Intuition\n Describe your first thoughts on how to solve this problem. \n- Using a Trie Data Structure:\nA Trie (prefix tree) is ideal for storing and quickly s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Using a Trie Data Structure:\nA Trie (prefix tree) is ideal for storing and quickly searching prefixes of strings. Each word can be inserted letter-by-letter, where each letter is a child node in the Trie. This structure makes it easy to check if a word can be built from smaller prefixes.\n- Building the Trie:\nThe insertKey function inserts each word into the Trie. The wordEnd boolean is set to true for nodes where a complete word ends, which helps differentiate between valid prefixes and complete words.\nDuring insertion, for each letter in the word, the function either moves to an existing child node (if that character is already part of a prefix) or creates a new child node (if it\u2019s a new character in the path).\n- Searching for the Longest Word:\nThe searchKey function checks if a word can be fully constructed from previous words in the Trie.\nFor each character in the word, it verifies that the current node\'s child node has wordEnd set to true. This ensures that every prefix of the word also exists as a standalone word.\nIf any prefix of the word is missing, the function returns false, which disqualifies the word.\n- Finding the Longest Word:\nAfter all words are inserted into the Trie, the longestWord function checks each word (from the end of the list) using searchKey.\nBy iterating backward, the code ensures that if there\u2019s a tie in length between words, the lexicographically smaller one (earlier in alphabetical order) is chosen.\nIf searchKey returns true for a word, it\u2019s a valid candidate for the longest buildable word.\n\n# Approach\n- Insert Words into Trie: Insert each word into a Trie where each node represents a character. Mark nodes where complete words end (wordEnd = true).\n\n- Check Buildable Words: For each word, check if it can be constructed from existing prefixes in the Trie. This is done by verifying each prefix up to the word\'s length has wordEnd = true.\n\n- Find Longest Word: Iterate through the words in reverse order to prioritize lexicographically smaller words if lengths are tied. Track the longest word that passes the buildable check.\n\n- Return Result: Return the longest word found that can be built incrementally from other words in the list.\n\n# Complexity\n- Time complexity:O(n*m) where n is length of an array of words and m is length of word\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n*m) where n is length of an array of words and m is length of word.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    struct TrieNode {\n        TrieNode* child[26];\n        bool wordEnd;\n\n        TrieNode() {\n            wordEnd = false;\n            for (int i = 0; i < 26; i++) {\n                child[i] = nullptr;\n            }\n        }\n    };\n\n    void insertKey(TrieNode* root, string s) {\n        TrieNode* cur = root;\n        for (auto c : s) {\n            if (cur->child[c - \'a\'] == nullptr) {\n                TrieNode* newNode = new TrieNode();\n                cur->child[c - \'a\'] = newNode;\n            }\n            cur = cur->child[c - \'a\'];\n        }\n        cur->wordEnd = true;\n    }\n    bool searchKey(TrieNode* root, string key) {\n        TrieNode* cur = root;\n        for (auto c : key) {\n            if (cur->child[c - \'a\'] == nullptr)\n                return false;\n            else if (cur->child[c - \'a\'] != nullptr and\n                     cur->child[c - \'a\']->wordEnd == false) {\n                return false;\n            }\n            cur = cur->child[c - \'a\'];\n        }\n\n        return true;\n    }\n    string longestWord(vector<string>& words) {\n        TrieNode* root = new TrieNode();\n        for (auto s : words) {\n            insertKey(root, s);\n        }\n        string res = "";\n        for (int i = words.size() - 1; i >= 0; i--) {\n            if (searchKey(root, words[i])) {\n                if(words[i].size()>res.size()){\n                    res=words[i];\n                }\n                else if(words[i].size()==res.size()){\n                    res=words[i]>res?res:words[i];\n                }\n            }\n        }\n\n        return res;\n    }\n};\n```
['C++']