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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public static string LongestWord(string[] words) {
6 Array.Sort(words, (a, b) => (a.Length == b.Length) ? string.Compare(a, b) : a.Length - b.Length);
7 HashSet<string> built = new HashSet<string> {""};
8 string res = "";
9 foreach (string word in words) {
10 if (built.Contains(word.Substring(0, word.Length - 1))) {
11 built.Add(word);
12 if (word.Length > res.Length) res = word;
13 }
14 }
15 return res;
16 }
17
18 public static void Main(string[] args) {
19 string[] words = {"w", "wo", "wor", "worl", "world"};
20 Console.WriteLine(LongestWord(words));
21 }
22}This solution uses a HashSet to keep track of all valid words that can be built. Array sorting is first completed based on a custom comparator which checks both word length and lexicographical order when necessary. The foreach loop effectively builds up the longest valid 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.
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.