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.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:
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.
C++
Java
Python
C#
JavaScript
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.
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:
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.
C++
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 | 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. |
Longest Word in Dictionary (LeetCode 720. Algorithm Explained) • Nick White • 18,469 views views
Watch 9 more video solutions →Practice Longest Word in Dictionary with our built-in code editor and test cases.
Practice on FleetCode