In this guide, you will get 720. Longest Word in Dictionary LeetCode Solution with the best time and space complexity. The solution to Longest Word in Dictionary problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given an array of strings words representing an English Dictionary, return 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.
Note that the word should be built from left to right with each additional character being added to the end of a previous word.
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”.
Constraints:
1 <= words.length <= 1000
1 <= words[i].length <= 30
words[i] consists of lowercase English letters.
720. Longest Word in Dictionary LeetCode Solution in C++
struct TrieNode {
vector<shared_ptr<TrieNode>> children;
const string* word = nullptr;
TrieNode() : children(26) {}
};
class Solution {
public:
string longestWord(vector<string>& words) {
for (const string& word : words)
insert(word);
return longestWordFrom(root);
}
private:
shared_ptr<TrieNode> root = make_shared<TrieNode>();
void insert(const string& word) {
shared_ptr<TrieNode> node = root;
for (const char c : word) {
const int i = c - 'a';
if (node->children[i] == nullptr)
node->children[i] = make_shared<TrieNode>();
node = node->children[i];
}
node->word = &word;
}
string longestWordFrom(shared_ptr<TrieNode> node) {
string ans = node->word ? *node->word : "";
for (shared_ptr<TrieNode> child : node->children)
if (child && child->word) {
string childWord = longestWordFrom(child);
if (childWord.length() > ans.length())
ans = childWord;
}
return ans;
}
}; /* code provided by PROGIEZ */
720. Longest Word in Dictionary LeetCode Solution in Java
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public String word;
}
class Solution {
public String longestWord(String[] words) {
for (final String word : words)
insert(word);
return longestWordFrom(root);
}
private TrieNode root = new TrieNode();
private void insert(final String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
final int i = c - 'a';
if (node.children[i] == null)
node.children[i] = new TrieNode();
node = node.children[i];
}
node.word = word;
}
private String longestWordFrom(TrieNode node) {
String ans = node.word == null ? "" : node.word;
for (TrieNode child : node.children)
if (child != null && child.word != null) {
String childWord = longestWordFrom(child);
if (childWord.length() > ans.length())
ans = childWord;
}
return ans;
}
} // code provided by PROGIEZ
720. Longest Word in Dictionary LeetCode Solution in Python
class Solution:
def longestWord(self, words: list[str]) -> str:
root = {}
for word in words:
node = root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['word'] = word
def dfs(node: dict) -> str:
ans = node['word'] if 'word' in node else ''
for child in node:
if 'word' in node[child] and len(node[child]['word']) > 0:
childWord = dfs(node[child])
if len(childWord) > len(ans) or (
len(childWord) == len(ans) and childWord < ans):
ans = childWord
return ans
return dfs(root) # code by PROGIEZ
