Longest Word in Dictionary
Understanding the Problem
We have a list of words and need to find the longest one that has a complete "chain" of prefixes in the dictionary. For a word like "world" to be valid, the dictionary must also contain "w", "wo", "wor", and "worl". Each prefix builds on the previous one by adding exactly one character at the end.
If two valid words have the same length, we pick the lexicographically smaller one. So between "apply" and "apple", we return "apple" because it comes first alphabetically.
This is a prefix-chain problem. A word of length k is buildable only if its prefix of length k-1 is also buildable. A word of length 1 is always buildable, since it is formed from the empty string by adding one character. This recursive structure points to two natural tools: sorting with a hash set, or a Trie.
Key Constraints:
words.length <= 1000→ The total number of words is small. Even O(n^2) approaches are feasible here.words[i].length <= 30→ Individual words are short. Operations on a single word (like extracting prefixes) are cheap.- Lowercase English letters only → Trie nodes need at most 26 children.
Approach 1: Brute Force (Check All Prefixes)
Intuition
Take each word, extract every prefix of that word, and check whether all those prefixes exist in the dictionary. If they do, the word is buildable. We track the longest buildable word seen so far, breaking ties by lexicographic order.
Checking "are all prefixes present" is equivalent to checking buildability: if every prefix of "world" ("w", "wo", "wor", "worl") is in the dictionary, then the chain exists by definition. To make those lookups O(1), we put all words into a hash set first.
Algorithm
- Insert all words into a hash set for O(1) lookups
- Initialize the result as an empty string
- For each word in the array:
- Check if every prefix of this word (from length 1 up to length - 1) exists in the hash set
- If all prefixes exist, compare this word against the current result: update if it is longer, or if it is the same length but lexicographically smaller
- Return the result
Example Walkthrough
Input:
The set is {"w", "wo", "wor", "worl", "world"}. We process the words in array order:
"w": no prefixes to check (length 1), buildable.result = "w"."wo": prefix"w"is in the set, buildable. Length 2 beats 1, soresult = "wo"."wor": prefixes"w","wo"are in the set, buildable.result = "wor"."worl": prefixes"w","wo","wor"are in the set, buildable.result = "worl"."world": prefixes"w","wo","wor","worl"are in the set, buildable.result = "world".
No word is longer than "world", so the answer is "world".
Output:
Code
- Time Complexity: O(n * L^2). We iterate through all n words. For each word of length L, we check up to L-1 prefixes, each costing O(L) for substring extraction.
- Space Complexity: O(n * L). The hash set stores all n words, each up to length L.
The brute force re-checks the full prefix chain for every word. Processing words from shortest to longest removes that redundancy: once shorter words are known to be buildable, each word only needs to verify its immediate prefix.
Approach 2: Sorting + HashSet
Intuition
If we sort the words first by length (shorter words first), then alphabetically within the same length, we can process words in order. By the time we encounter a word of length k, all words of length k-1 have already been processed.
A word is buildable if its prefix of length k-1 (the word minus its last character) is already in our set of buildable words. Words of length 1 are always buildable since they are built from the empty string by adding one character.
Sorting shortest-first, then alphabetically within a length, gives two guarantees. First, when we reach a word, its one-character-shorter prefix has already been processed, so if that prefix was buildable it is already in the set. Second, among words of equal length the alphabetically smallest is processed first, so the first buildable word at any length is the tie-break winner at that length.
Checking only the immediate prefix is sufficient because buildability is transitive. A word enters the set only when its immediate prefix is in the set, and that prefix entered only when its own prefix was in the set. So membership in the set already certifies the full chain back to the empty string, and re-verifying it is unnecessary.
Algorithm
- Sort the words by length first, then lexicographically
- Create a hash set of buildable words, initialized with an empty string ""
- Initialize the result as an empty string
- For each word in sorted order:
- Check if the prefix of length (word.length - 1) is in the buildable set
- If yes, add this word to the buildable set
- Update the result if this word is longer than the current result
- Return the result
Example Walkthrough
Code
- Time Complexity: O(n L log n). Sorting takes O(n L log n) where L is the max word length. The single pass through the sorted array takes O(n * L) for substring operations. Sorting dominates.
- Space Complexity: O(n * L). The hash set stores up to n words, each of length up to L.
The sorting approach spends O(n L log n) on the sort and creates a substring per word. A Trie stores shared prefixes once and lets us walk the prefix chains directly, dropping the sort and giving O(n * L) overall.
Approach 3: Trie with DFS
Intuition
A Trie (prefix tree) maps the problem directly onto its structure, since every node in a Trie represents one prefix. We insert all words into a Trie, marking which nodes end a word, then search for the longest path from the root where every node along the way is a complete word.
If a node's prefix is itself a word in the dictionary (its isEnd flag is true), we can build up to that point. The answer is the deepest node reachable by following only edges into end-of-word nodes. A DFS from the root that explores children in alphabetical order and descends only into end-of-word nodes finds it: exploring a-z first means the deepest node it records is also the lexicographically smallest at that depth.
Algorithm
- Build a Trie by inserting all words
- Run DFS from the root of the Trie
- At each node, only visit children that are marked as the end of some word
- Track the deepest valid path encountered during DFS
- If two paths have the same depth, prefer the lexicographically smaller one (handled by exploring children a-z)
- Return the word corresponding to the deepest valid path
Example Walkthrough
Code
- Time Complexity: O(n L). Building the Trie takes O(n L) where n is the number of words and L is the max word length. The DFS visits each node at most once.
- Space Complexity: O(n L). The Trie stores up to n L nodes, each with an array of 26 children pointers.