Problem Description
Given a list of words representing an English dictionary, find the longest word that can be built one character at a time such that each prefix of the word is also present in the dictionary. When multiple words meet this condition, return the one which is lexicographically smallest. If no such word exists, return an empty string.
Key Insights
- The word must be built character by character; hence every prefix (removing one character from the end at a time) must exist in the dictionary.
- Sorting the input list can help in ensuring that smaller words (prefixes) are processed first.
- Using a hash set to store valid words enables rapid prefix checks.
- Lexicographical order plays a role when words have the same length.
Space and Time Complexity
Time Complexity: O(n * L + n log n) where n is the number of words and L is the maximum length of a word (n * L for prefix checking, and n log n for sorting). Space Complexity: O(n * L) for storing words in the set.
Solution
The approach begins by sorting the list of words. Sorting is done primarily by word length and secondarily by lexicographical order so that when we iterate through the words, all possible prefixes for a word have already been considered. Initialize a set to keep track of valid words that can be built one character at a time. For each word in the sorted list, check if all its prefixes (word without the last character progressively) exist in the set. If a word qualifies, add it to the set and check if it should be the new result based on length and lexicographical order. The set lookup ensures that checking each prefix is efficient.