To solve this problem, iterate through words and use a Set to check if every prefix of each word exists in the dictionary. This guarantees the longest word can be formed step by step. For multiple valid words, return the lexicographically smallest one.
Problem Statement
Given a list of words representing an English dictionary, return the longest word that can be built one character at a time, each prefix of the word must also be a word in the list. If there is more than one possible word, return the one with the smallest lexicographical order.
A word can be constructed by successively adding characters to its previous form. If no such word exists, return an empty string.
Examples
Example 1
Input: words = ["w","wo","wor","worl","world"]
Output: "world"
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"
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".
Constraints
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 30
- words[i] consists of lowercase English letters.
Solution Approach
Array Scanning with Hash Lookup
Iterate through each word in the dictionary and check if all its prefixes exist using a Set. If so, it's a valid candidate. Track the longest word while considering lexicographical order.
Efficient Word Validation
By maintaining a Set of words, checking whether a prefix exists becomes a constant-time operation. This enables the solution to handle the problem efficiently even for larger inputs.
Handling Lexicographical Order
While iterating through the dictionary, if a valid word has the same length as a previously found word, compare them lexicographically and keep the smallest.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(\sum w_i) |
| Space | O(\sum w_i) |
Time complexity is O(∑ w_i) due to iterating over all words and checking their prefixes, and space complexity is O(∑ w_i) because of storing words in a Set for fast lookups.
What Interviewers Usually Probe
- Evaluate whether the candidate efficiently uses hash sets for prefix checking.
- Assess how well the candidate handles lexicographical order when there are multiple valid longest words.
- Check if the candidate optimizes for time and space when validating word prefixes.
Common Pitfalls or Variants
Common pitfalls
- Failing to use a Set to quickly check word prefixes can result in slower solutions.
- Not handling multiple valid words with the same length but different lexicographical orders correctly.
- Overlooking edge cases where no valid word can be built from the dictionary.
Follow-up variants
- Consider cases where the input list contains a mix of short and long words.
- Test the solution against a dictionary with words having the same prefixes but different lengths.
- Evaluate performance when all words in the dictionary are valid and can be built from each other.
How GhostInterview Helps
- GhostInterview provides step-by-step guidance to solve the problem efficiently using hash sets and string manipulation techniques.
- The tool highlights common mistakes to avoid, ensuring optimal solutions for large inputs.
- GhostInterview also helps in practicing how to prioritize lexicographical order when dealing with multiple valid answers.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the optimal way to check if all prefixes of a word exist in the dictionary?
Use a Set to store words for constant-time lookups, then check each prefix of the word during the iteration.
How do I handle cases where multiple longest words are valid?
Track the lexicographically smallest word when multiple words of the same length are found.
How can I optimize my solution for large inputs?
Ensure the Set lookup is used to validate prefixes and avoid unnecessary repeated iterations over the words.
What should I do if no valid word can be built from the dictionary?
Simply return an empty string in this case.
What is the expected time complexity for this problem?
The time complexity is O(∑ w_i), where w_i is the length of each word. This accounts for checking all prefixes of each word.
Need direct help with Longest Word in Dictionary instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Longest Word in Dictionary from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve Top K Frequent Words by counting each word, then ordering ties alphabetically so frequency wins before lexicographic comparison.
Open problem page#792 Number of Matching SubsequencesGiven a string s and a list of words, count how many words are subsequences of s using efficient array scanning and hash lookup.
Open problem page#721 Accounts MergeMerge accounts by connecting emails and returning each user's sorted email list using array scanning and hash lookup efficiently.
Open problem page