Medium · Trie Prefix Validation
Understand → Visualise → Practice.
Return the longest word for which every non-empty prefix is also in the dictionary; break ties lexicographically.
In a trie of all words, a word can be built one letter at a time exactly when every node on its path is marked as a word end. DFS along marked nodes only.
Insert every word and mark word ends.
DFS from the root, entering a child only if it ends a word.
Track the longest word reached; on ties keep the lexicographically smaller one.
O(total characters) time and space.
Checking only that the word minus its last letter exists misses gaps further back.
Read the full guide first: Tries and Prefix Search.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.