Longest Word in Dictionary
Given a list of strings words
representing an English Dictionary, find the longest word in words
that can be built one character at a time by other words in words
. If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.
Example 1:
Input:
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation:
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
Example 2:
Input:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation:
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".
Note:All the strings in the input will only contain lowercase letters.The length of words
will be in the range [1, 1000]
.The length of words[i]
will be in the range [1, 30]
.
Solutions
🧠 Cpp
#define all(x) begin(x),end(x)
class Solution
{
struct TrieNode
{
char value = ' ';
bool is_wordend = false;
vector<shared_ptr<TrieNode>> nodes;
};
shared_ptr<TrieNode> createTrie(const vector<string>& words)
{
auto root = make_shared<TrieNode>();
//translate vector of strings into trie
for(const auto &str : words)
{
//start inserting new word from trie root
auto trie_pointer = root;
for(auto ch_iter = begin(str); ch_iter < end(str); ++ch_iter)
{
const char ch = *ch_iter;
const bool char_present_in_trie = std::any_of(all(trie_pointer->nodes),
[&trie_pointer, ch](auto node)
{
bool found = node->value == ch;
if (found)
trie_pointer = node;
return found;
});
//insert new node
if(!char_present_in_trie)
{
auto node = make_shared<TrieNode>();
node->value = ch;
trie_pointer->nodes.push_back(node);
trie_pointer = node;
}
if(ch_iter == prev(end(str)))
trie_pointer->is_wordend = true;
}
}
return root;
}
public:
vector<string> get_words_formed_by_words(const shared_ptr<TrieNode> root)
{
vector<string> res;
for(auto &leaf : root->nodes)
{
if(leaf->is_wordend)
{
res.emplace_back(1, leaf->value);
vector<string> subres = get_words_formed_by_words(leaf);
if(!subres.empty())
{
string last_letter = res.back();
for(auto &str : subres)
res.push_back(last_letter + str);
}
}
}
return res;
}
string longestWord(vector<string>& words)
{
//O(n)
auto root = createTrie(words);
//O(n)
vector<string> wfbw = get_words_formed_by_words(root);
//O(n)
return *max_element(all(wfbw),
[](auto a, auto b)
{
return a.size() == b.size() ?
a > b :
a.size() < b.size();
});
}
};
Last updated
Was this helpful?