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.
1import java.util.HashSet;
2import java.util.Arrays;
3
4public class Solution {
5 public static String longestWord(String[] words) {
6 Arrays.sort(words, (a, b) -> (a.length() == b.length() ? a.compareTo(b) : Integer.compare(a.length(), b.length())));
7 HashSet<String> built = new HashSet<>();
8 built.add("");
9 String res = "";
10 for (String word : words) {
11 if (built.contains(word.substring(0, word.length() - 1))) {
12 built.add(word);
13 if (word.length() > res.length()) res = word;
14 }
15 }
16 return res;
17 }
18
19 public static void main(String[] args) {
20 String[] words = {"w", "wo", "wor", "worl", "world"};
21 System.out.println(longestWord(words));
22 }
23}In Java, the solution employs a HashSet to keep track of valid prefixes. Sorting is done via a custom comparator that sorts by length and lexicographical order. This helps in efficiently deciding which word is substantiated as a valid word as we iterate through the sorted array.
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.