# 720. 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]`.

``````class Solution {
public:
string longestWord(vector<string>& words) {
string res = "";
int mxLen = 0;
unordered_set<string> s(words.begin(), words.end());
queue<string> q;
for (string word : words) {
if (word.size() == 1) q.push(word);
}
while (!q.empty()) {
string t = q.front(); q.pop();
if (t.size() > mxLen) {
mxLen = t.size();
res = t;
} else if (t.size() == mxLen) {
res = min(res, t);
}
for (char c = 'a'; c <= 'z'; ++c) {
t.push_back(c);
if (s.count(t)) q.push(t);
t.pop_back();
}
}
return res;
}
};
``````

``````class Solution {
public:
string longestWord(vector<string>& words) {
string res = "";
int mxLen = 0;
unordered_set<string> s(words.begin(), words.end());for (string word : words) {
if (word.size() == 1) helper(s, word, mxLen, res);
}
return res;
}
void helper(unordered_set<string>& s, string word, int& mxLen, string& res) {
if (word.size() > mxLen) {
mxLen = word.size();
res = word;
} else if (word.size() == mxLen) {
res = min(res, word);
}
for (char c = 'a'; c <= 'z'; ++c) {
word.push_back(c);
if (s.count(word)) helper(s, word, mxLen, res);
word.pop_back();
}
}
};
``````

``````class Solution {
public:
string longestWord(vector<string>& words) {
string res = "";
unordered_set<string> s;
sort(words.begin(), words.end());
for (string word : words) {
if (word.size() == 1 || s.count(word.substr(0, word.size() - 1))) {
res = (word.size() > res.size()) ? word : res;
s.insert(word);
}
}
return res;
}
};
``````

Longest Word in Dictionary through Deleting

Implement Magic Dictionary

https://discuss.leetcode.com/topic/109643/java-c-clean-code

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation