Longest Word with All Prefixes
MediumEvery prefix must itself be a word
Problem
Given a list of words, find the longest word such that every prefix of it is also present in the list (ties broken lexicographically).
In a trie, find the deepest word whose every prefix is also a complete word.
The idea
Insert every word, then check each one by walking its path and requiring the end-of-word flag at every single node along the way. That check is exactly the definition, and the trie makes it O(length) rather than a lookup per prefix.
The trick
- Fail the moment any intermediate node is not itself a word end.
- Ties break lexicographically, so sort the candidates or compare as you go.
Step 1 of 5. The trie already stores "cat" and "car". Insert "cap" — walk down, creating nodes only where they're missing.
Descend one node per letter.
1insert(word) {2 let node = this.root;3 for (const ch of word) {4 if (!node.children.has(ch)) node.children.set(ch, new TrieNode());5 node = node.children.get(ch);6 }7 node.isEnd = true;8}Input
- nodes
- 5, 4 edges
Memory
- matched
- —
Output
- created
- —
- inserted
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- words = ["n","ni","nin","ninj","ninja","nk"]
- Output:
- "ninja"
- Explanation:
- Every prefix of 'ninja' also exists.
Example 2
- Input:
- words = ["a","banana","app","appl","ap","apply","apple"]
- Output:
- "apple"
- Explanation:
- 'apple' is buildable one letter at a time.
Example 3
- Input:
- words = ["abc"]
- Output:
- ""
- Explanation:
- 'ab' missing → no valid word.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.