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.
1def longestWord(words):
2 words.sort(key=lambda x: (len(x), x))
3 built, res = {""}, ""
4 for word in words:
5 if word[:-1] in built:
6 built.add(word)
7 if len(word) > len(res):
8 res = word
9 return res
10
11words = ["w", "wo", "wor", "worl", "world"]
12print(longestWord(words))Python's concise syntax and dynamic typing make this implementation straightforward. It utilizes a prefix check with a set and manages the longest word in a single iteration over the sorted words list. Python's built-in sorting handles the ordering based on length and lexicography.
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.