Longest Word in Dictionary
Given an array of strings words, return the longest word that can be built one character at a time by other words in the array. If there is a tie, return the lexicographically smallest one.
Intuition
A word can be 'built one character at a time' only if every prefix of that word is also in the dictionary. For example, world is buildable only if w, wo, wor, worl, and world are all present. Checking every prefix in a hash set works, but a trie makes the structure visible: insert all words, then walk the trie and only continue down branches where every node along the path is a word-end. The deepest reachable node on such a path gives the longest buildable word. Among ties, lexicographic order is handled naturally if you explore children in alphabetical order.
When a problem asks whether a word can be formed by progressively adding characters, and every intermediate stage must also be valid, the shape is 'does every prefix exist?' A trie makes this a depth-first walk with a single guard: only continue through word-end nodes. Sorting plus hash-set prefix checks is the alternative, but the trie captures the same idea structurally.
Approach
Insert all words into a trie, marking word-end nodes
Build a standard trie from the input words. At the node where each word terminates, set a flag to mark it as a complete word. This is the foundation — the trie captures all prefix relationships in one structure.
DFS the trie, only following paths through word-end nodes
Starting from the root, explore each child. But only continue into a child node if that node is marked as a word-end — meaning the prefix up to that point is itself in the dictionary. If a node is not a word-end, that prefix is missing and no longer word built through it is valid. Track the longest word found during the search.
Break ties lexicographically by exploring children in order
At each trie node, iterate over children in alphabetical order (a before b, etc.). Because you explore a before b, the first longest word you find is automatically the lexicographically smallest among ties. Update the best answer only when you find a strictly longer word. Time is O(total characters) for both construction and the DFS.
Solution
Common pitfalls
Continuing DFS through nodes that are not word-ends
if node.children[ch]:
dfs(node.children[ch])if node.children[ch] and node.children[ch].is_end:
dfs(node.children[ch])A node that is not a word-end means that prefix is not in the dictionary, so the word cannot be built one character at a time. Skipping the check returns words whose intermediate prefixes are missing.
Updating the best answer on equal length instead of strictly longer
if len(current) >= len(best):
best = currentif len(current) > len(best):
best = currentWith >=, a later word of the same length overwrites the earlier one. Since DFS explores alphabetically, the earlier one is lexicographically smaller — which is the correct tiebreaker. Using >= picks the larger one.
Forgetting to add the root's children as starting points
dfs(root, '')
for ch in sorted(root.children):
if root.children[ch].is_end:
dfs(root.children[ch], ch)The root itself represents the empty string, not a word. You must start from children that are marked as word-ends (single-character words in the dictionary). Starting from root without checking is_end on children allows paths that begin with a missing single letter.
Edge cases
Each single-character word is trivially buildable (its only prefix is itself). The answer is the lexicographically smallest single character.
The DFS never goes deeper than one level. The result is the smallest single-letter word, or empty string if even single letters are missing — though the constraint guarantees at least one word.
Alphabetical DFS order ensures the lexicographically smaller one is found first, and we only update on strictly longer words, so the smaller one wins.