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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <stdbool.h>
5
6int compare(const void *a, const void *b) {
7 const char *word1 = *(const char **)a;
8 const char *word2 = *(const char **)b;
9 if (strlen(word1) == strlen(word2)) {
10 return strcmp(word1, word2);
11 }
12 return strlen(word1) - strlen(word2);
13}
14
15bool canBeBuilt(char *word, char **set, int setLen) {
16 char prefix[strlen(word)];
17 strncpy(prefix, word, strlen(word) - 1);
18 prefix[strlen(word) - 1] = '\0';
19 for (int i = 0; i < setLen; i++) {
20 if (strcmp(set[i], prefix) == 0) {
21 return true;
22 }
23 }
24 return false;
25}
26
27char* longestWord(char** words, int wordsSize) {
28 qsort(words, wordsSize, sizeof(char *), compare);
29 char **set = (char **)malloc(wordsSize * sizeof(char *));
30 int setLen = 0;
31 set[setLen++] = "";
32 char *longestWord = "";
33 for (int i = 0; i < wordsSize; i++) {
34 if (canBeBuilt(words[i], set, setLen)) {
35 set[setLen++] = words[i];
36 if (strlen(words[i]) > strlen(longestWord)) {
37 longestWord = words[i];
38 }
39 }
40 }
41 free(set);
42 return longestWord;
43}
44
45int main() {
46 char *words[] = {"w", "wo", "wor", "worl", "world"};
47 printf("%s\n", longestWord(words, 5));
48 return 0;
49}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.
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.