Sponsored
Sponsored
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
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.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
#include <algorithm>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool end_of_word = false;
};
class Solution {
public:
string longestWord(vector<string>& words) {
TrieNode* root = new TrieNode();
for (string word : words) {
TrieNode* current = root;
for (char ch : word) {
if (!current->children.count(ch)) {
current->children[ch] = new TrieNode();
}
current = current->children[ch];
}
current->end_of_word = true;
}
string result;
for (string word : words) {
if (canBuild(root, word) && (word.size() > result.size() || (word.size() == result.size() && word < result))) {
result = word;
}
}
return result;
}
private:
bool canBuild(TrieNode* root, const string& word) {
TrieNode* current = root;
for (char ch : word) {
current = current->children[ch];
if (!current->end_of_word) {
return false;
}
}
return true;
}
};
int main() {
Solution solution;
vector<string> words = {"w", "wo", "wor", "worl", "world"};
cout << solution.longestWord(words) << endl;
return 0;
}In C++, the Trie data structure is implemented with unordered_map to facilitate quick access to children by character. The insertion of words in Trie and subsequent validation of words based on availability of prefixes in the Trie is critical for constructing the longest valid word.