Longest Word in Dictionary
Problem Description
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.
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
The brute force approach involves iterating through each word and checking if all its prefixes exist in the given list. We can achieve this by using a HashSet to store all words and checking if each prefix of a word exists in the set. If so, keep track of the longest valid word encountered so far.
Steps:
- Insert all words into a HashSet for fast look-up.
- Iterate over each word. For each word, check if all of its prefixes exist using the HashSet.
- If all prefixes of a word exist, compare it with the current longest word and update if necessary.
- In cases where two valid words have the same length, choose the lexicographical smaller one.
Code:
- Time Complexity: O(N * M), where N is the number of words and M is the maximum length of a word (as we need to check each prefix).
- Space Complexity: O(N * M), to store all the words in the HashSet.
2. Trie-based Approach
Intuition:
A Trie is an efficient data structure to store and retrieve words, especially useful in prefix queries. By inserting all words into a Trie, we can efficiently check if a word can be built by other words. We traverse the Trie to find the deepest node that represents a complete buildable word, which will be our answer.
Steps:
- Insert all words into the Trie and mark the end of each complete word.
- Perform a depth-first search (DFS) on the Trie, keeping track of the longest word that can be constructed step-by-step.
- Continue traversal only if the current path represents a complete word until that node.
Code:
- Time Complexity: O(N * M), where N is the number of words and M is the maximum length of the words. Each insertion and search operation in the Trie is proportional to the length of the word.
- Space Complexity: O(26 * N * M), for storing N words each having a maximum length M in the Trie. The 26 factor is for the 26 letters of the English alphabet.