Longest Word in Dictionary medium
Description
Given a list of words, return the longest word that can be built one character at a time by other words in the list — i.e. every prefix of it (of length 1, 2, …) must also be in the list. If there are ties, return the lexicographically smallest.
Examples
> words = ["w","wo","wor","worl","world"]
Output: "world" # w -> wo -> wor -> worl -> world, each a word
> words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple" # apple is buildable (a,ap,app,appl,apple); "apply" too,
# but "apple" < "apply" lexicographicallyConstraints
1 <= words.length <= 1000, total characters ≤10^6, lowercase.
Intuition
Insert all words into a trie. A word qualifies iff every node along its path is marked end-of-word — that’s precisely “every prefix is also a word.” DFS the trie, only descending into children that are themselves end-of-word, and track the deepest (then lexicographically smallest) word reachable. Visiting children in alphabetical order makes the lexicographic tie-break automatic.
Code
The lexicographic tie-break is free if you DFS in alphabetical order. Iterating children a → z means the first word of a given maximum length you record is automatically the smallest. Only replace best when you find a strictly longer word (>, not >=), so an equal-length-but-later word never overwrites the earlier (smaller) one.
Analysis
- Time:
O(total characters)to build the trie +O(total characters)to DFS — each node visited once. - Space:
O(total characters)for the trie,O(max word length)recursion.
Same skin
- Replace Words — both hinge on end-of-word nodes along a path.
- Concatenated Words / Word Break — “is this buildable from dictionary pieces?” generalizes this idea.
- Implement Trie — the base structure plus a constrained DFS.