Longest Word in Dictionary - Solution & Explanation
Problem Statement
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.
Approach Overview
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 1: Sorting and Set-based Verification
This approach involves sorting the words array. By sorting, words that could potentially be built upon would appear earlier in the list. After sorting, we use a set to keep track of words that can be built character by character.
The process is as follows:
- Sort the words array first based on length, then lexicographically.
- Initialize a set with an empty string.
- Iterate through each word in the sorted array:
- Check if the prefix of the word (without the last character) exists in the set.
- If it exists, add the whole word to the set.
- Track the longest word found during the iteration.
This is efficient due to the pre-sorting which allows easy checking and ensures we are building words correctly by the constraints given.
The solution first sorts the array based on length and lexicographical order. A helper function, canBeBuilt, checks if the current word can be constructed from words already existing in the set. We dynamically maintain our set using a simple array to track these valid words.
The function returns the longest valid word found during this process. Note that memory handling is crucial in C, hence we dynamically allocate and free the set array.
Complexity
Time complexity: O(N log N + N * M), where N is the number of words and M is the average length of the words. Sorting takes O(N log N) and checking prefixes takes O(N * M).
Space complexity: O(N * M), where M is the length of the longest word.
Approach 2: Trie-based Approach
This approach uses a Trie (prefix tree) to store the words. By utilizing this data structure, we aim to verify if a word can be constructed by progressively building on its prefixes.
The steps are:
- Build a Trie from the words array.
- For each word, check if all its prefixes are present in the Trie.
- Track the longest word that meets the criterion.
- If multiple words have the same length, select the lexicographically smallest one.
This combines efficient storage and lookup, with Prefix trees naturally lending themselves to this problem due to their structure.
This Python solution involves first inserting all words into a Trie structure and then checking each sorted word to verify that every prefix exists within the Trie. The check is aided by the use of an end_of_word flag to determine the presence of complete valid prefixes every step of the way.
Complexity
Time complexity: O(N * M), where creating the Trie and checking word validity both operate over each character of every word.
Space complexity: O(N * M) for the Trie data structure.
Approach 3: Trie
We can use a trie to store all the words, then traverse all the words to determine if the current word can be formed by adding one letter at a time from other words in the trie. Find the longest word that meets the condition and has the smallest lexicographical order.
The time complexity is O(L), and the space complexity is O(L), where L is the sum of the lengths of all words.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sorting and Set-based Verification | Time complexity: O(N log N + N * M), where N is the number of words and M is the average length of the words. Sorting takes O(N log N) and checking prefixes takes O(N * M). Space complexity: O(N * M), where M is the length of the longest word. |
| Trie-based Approach | Time complexity: O(N * M), where creating the Trie and checking word validity both operate over each character of every word. Space complexity: O(N * M) for the Trie data structure. |
| Trie | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Longest Word in Dictionary (LeetCode 720. Algorithm Explained) • Nick White • 19,389 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Word in Dictionary easy or hard?
How to solve Longest Word in Dictionary in O(n)?
What is the best approach for Longest Word in Dictionary?
What data structure is used in Longest Word in Dictionary?
What is the time complexity of Longest Word in Dictionary?
Longest Word in Dictionary Python or Java solution approach?
Is Longest Word in Dictionary asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Longest Word in Dictionary with our built-in code editor and test cases.
Practice on FleetCode