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.
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.
1function longestWord(words) {
2 words.sort((a, b) => a.length === b.length ? (a < b ? -1 : 1) : a.length - b.length);
3 let built = new Set([""]);
4 let res = "";
5 for (let word of words) {
6 if (built.has(word.slice(0, -1))) {
7 built.add(word);
8 if (word.length > res.length) res = word;
9 }
10 }
11 return res;
12}
13
14const words = ["w", "wo", "wor", "worl", "world"];
15console.log(longestWord(words));In JavaScript, the solution leverages Set for quick prefix checks. Sorting is handled with Array sort method using a comparator that first checks length and then lexicographical order. This allows direct evaluation of the validity of each word in sequence.
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.
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.
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.end_of_word = False
5
6class Solution:
7 def longestWord(self, words):
8 root = TrieNode()
9 for word in sorted(words):
10 current_node = root
11 for char in word:
12 if char not in current_node.children:
13 current_node.children[char] = TrieNode()
14 current_node = current_node.children[char]
15 current_node.end_of_word = True
16
17 def canBuild(word):
18 current_node = root
19 for char in word:
20 current_node = current_node.children.get(char)
21 if not current_node.end_of_word:
22 return False
23 return True
24
25 longest = ""
26 for word in sorted(words, key=lambda x: (-len(x), x)):
27 if canBuild(word) and len(word) > len(longest):
28 longest = word
29 return longest
30
31words = ["w", "wo", "wor", "worl", "world"]
32solution = Solution()
33print(solution.longestWord(words))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.