Watch 10 video solutions for Longest Word in Dictionary, a medium level problem involving Array, Hash Table, String. This walkthrough by Nick White has 19,221 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.
If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.
Note that the word should be built from left to right with each additional character being added to the end of a previous word.
Example 1:
Input: words = ["w","wo","wor","worl","world"] Output: "world" Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
Example 2:
Input: words = ["a","banana","app","appl","ap","apply","apple"] Output: "apple" Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".
Constraints:
1 <= words.length <= 10001 <= words[i].length <= 30words[i] consists of lowercase English letters.Problem Overview: You are given a list of words. The task is to find the longest word that can be built one character at a time by other words in the same list. Every prefix of the word must also exist in the dictionary. If multiple answers exist, return the lexicographically smallest one.
Approach 1: Sorting and Set-based Verification (O(n log n) time, O(n) space)
This approach sorts the word list lexicographically so smaller words appear before their extensions. Iterate through the sorted list and maintain a HashSet of valid buildable words. A word is valid if its prefix word[:-1] already exists in the set. If valid, insert it into the set and update the current best answer when its length is greater than the previous result. Sorting ensures that shorter prefixes are processed before longer candidates. This method relies heavily on fast membership checks using a hash table and works well for most interview constraints.
Approach 2: Trie-based Approach (O(n * L) time, O(n * L) space)
A Trie stores all words while preserving prefix relationships. Insert every word into the Trie and mark nodes that represent completed words. Then perform DFS or iterate through the words to verify that every prefix node along the path is marked as a valid word. Only paths where each intermediate node represents a completed word are considered buildable. Track the longest word encountered, resolving ties using lexicographic order. This approach leverages the natural prefix structure of a Trie and avoids repeated substring checks common with plain string operations.
The Trie solution scales well when the dataset contains many shared prefixes because each character is processed once during insertion and traversal. However, it requires more memory due to storing nodes for each character.
Recommended for interviews: The sorting + hash set approach is typically expected in interviews. It is concise, easy to reason about, and demonstrates efficient use of sorting and hash lookups. The Trie solution shows deeper knowledge of prefix data structures and is a strong alternative when discussing optimizations or follow‑up questions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Hash Set Verification | O(n log n) | O(n) | General interview solution. Simple implementation using sorting and fast prefix checks. |
| Trie-based Prefix Validation | O(n * L) | O(n * L) | Useful when many words share prefixes or when demonstrating Trie knowledge. |