Longest Word in Dictionary
Longest Word in Dictionary is LeetCode 720 (Medium). You get an array words of lowercase English strings. Find the longest word that can be built one letter at a time from other words in the array.
- A word of length
kis buildable when its prefixes of length 1, 2, …,k − 1are all inwords. Every step must add exactly one letter at the end. - A one-letter word is always buildable: it has no shorter prefix to check.
- If several buildable words share the maximum length, return the one that comes first in lexicographical order.
- If no word is buildable, return the empty string.
There are at most 1,000 words of at most 30 letters, so checking every prefix of every word is cheap; the interest is in doing it cleanly and getting the tie rule right.
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 30
- words[i] consists of lowercase English letters.
Intuition
Put every word into a trie and mark the node where each word ends. A root-to-node path spells a prefix, so "every prefix is a word" becomes visible: every node on the path ends a word.
The problem turns into a walk that only steps into word-ending children. Every node it reaches is buildable, and anything behind a non-word node has a missing prefix, so the deepest node reached is the answer.
Trying children in alphabetical order settles ties for free: the walk meets words in dictionary order, so the first word found at the maximum length is the smallest one.
"Every prefix must also be present" is the signal for a trie, because a trie stores all prefixes of a word along one path. The same walk appears in Longest Word With All Prefixes (LeetCode 1858), and the trie itself is Implement Trie (LeetCode 208). The longest word in dictionary LeetCode problem is the gentlest of these: one insert pass, one restricted DFS.
Approach
Before reading on: with words = ["b", "ba", "bad", "a", "ab", "abd"], which buildable words have the maximum length, and which one should be returned? Then decide whether you update the answer on > or on >= if you scan candidates in alphabetical order.
Two ways to solve it
Insert every word into a trie, then walk only through nodes where a word ends.
- Speed: each letter is touched a constant number of times.
- Ties: alphabetical child order settles them.
- Shows: why prefixes form one path.
The structure the problem is really about.
Sort the words, then keep a word when the word minus its last letter is already in the set of built words.
- Speed: the sort adds a log factor.
- Ties: sorted order settles them too.
- Length: about six lines.
Quickest to write from memory.
The trie checks every prefix in one walk with no sort, so it is the faster of the two. The steps, code and live demo below follow the trie; the sort + set code comes after the demo.
Build the trie
Insert each word letter by letter, creating child nodes as needed, and store the word itself at its last node. That stored word marks a word-ending node, and it saves rebuilding the string from the path later. The root stores nothing.
Walk only through word-ending children
From the root, visit children in order a to z and skip any child that does not end a word. Every word below a skipped node would need that node as one of its steps, so the whole subtree is pruned without being looked at.
Keep the longest, earliest word
At each visited node, replace best only when its word is strictly longer, then continue into its children. Because the walk reaches words alphabetically, the first word of each length is already the smallest, and a strict > never lets a later one replace it.
Return the result
After the walk, return best. It starts as "", so when no one-letter word exists the root has no word-ending child, nothing is visited, and the empty string comes back without a special case.
Why the walk is correct
A node is visited exactly when every node on its path ends a word, which is the definition of buildable. Visiting children alphabetically is a pre-order traversal, so words of equal length are met in lexicographic order and the first one is kept.
Longest Word in Dictionary solution in Python | C++ | Java
> keeps apple.Sort + hash set
Sorting puts every word after its own prefixes, so a single pass can test word[:-1] against the set of words already proven buildable. In longest word in dictionary Python code this is the shortest version.
Common pitfalls
Checking only the one-letter-shorter prefix
if word[:-1] in words_set:
candidates.append(word)if word[:-1] in built:
built.add(word)With ["ab", "abc"], "abc" passes because "ab" is in the list, yet "a" is not, so neither word is buildable. The prefix has to be buildable itself, so test against the set of words already proven buildable, processed in sorted order.
Updating the answer on >=
if len(child["$"]) >= len(best):
best = child["$"]if len(child["$"]) > len(best):
best = child["$"]The walk meets words in alphabetical order, so the first word of the maximum length is the right one. >= replaces it with every later word of the same length and returns the largest instead, for example "apply" instead of "apple".
Visiting children in insertion order
for ch in node:
...for ch in sorted(k for k in node if k != "$"):
...A Python dict iterates in insertion order, which follows the input, not the alphabet. The tie rule then depends on how the words were listed. C++ and Java arrays indexed by ch - 'a' are already in order.
Edge cases
The root has no word-ending child, so the walk visits nothing and the answer is "", even if long words exist.
Complexity
Three "longest word" problems that are easy to mix up
They share a name pattern but test different things.
| Problem | Word must | Tie-break | Usual tool |
|---|---|---|---|
| Longest Word in Dictionary (720) | have every prefix in the list | lexicographically smallest | trie or sort + set |
| Longest Word With All Prefixes (1858) | have every prefix in the list (premium variant) | lexicographically smallest | trie |
| Longest Word in Dictionary through Deleting (524) | be a subsequence of a given string s | lexicographically smallest | two pointers per word |
Longest Word in Dictionary FAQ
Why does DFS in alphabetical order give the lexicographically smallest answer?
A pre-order walk that tries children a to z lists the words of a trie in dictionary order. Among words of the maximum length the walk therefore reaches the smallest first, and a strict > comparison never lets a later word of equal length replace it.
What are the time and space complexity of LeetCode 720?
O(L) time and space for the trie solution, where L is the total length of all words.