Longest Word in Dictionary
Problem
Given a list of strings words, 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 answer, return the lexicographically smallest one. If there is no such answer, return an empty string.
words = ["w","wo","wor","worl","world"]"world"def longest_word(words):
s = set(words)
words.sort(key=lambda w: (-len(w), w))
for w in words:
if all(w[:i] in s for i in range(1, len(w))):
return w
return ""function longestWord(words) {
const s = new Set(words);
words.sort((a, b) => b.length - a.length || a.localeCompare(b));
for (const w of words) {
let ok = true;
for (let i = 1; i < w.length; i++) if (!s.has(w.slice(0, i))) { ok = false; break; }
if (ok) return w;
}
return "";
}class Solution {
public String longestWord(String[] words) {
Set<String> s = new HashSet<>(Arrays.asList(words));
Arrays.sort(words, (a, b) -> a.length() != b.length() ? b.length() - a.length() : a.compareTo(b));
for (String w : words) {
boolean ok = true;
for (int i = 1; i < w.length(); i++) if (!s.contains(w.substring(0, i))) { ok = false; break; }
if (ok) return w;
}
return "";
}
}string longestWord(vector<string>& words) {
unordered_set<string> s(words.begin(), words.end());
sort(words.begin(), words.end(), [](const string& a, const string& b) {
return a.size() != b.size() ? a.size() > b.size() : a < b;
});
for (auto& w : words) {
bool ok = true;
for (int i = 1; i < (int)w.size(); i++) if (!s.count(w.substr(0, i))) { ok = false; break; }
if (ok) return w;
}
return "";
}Explanation
A word is "buildable" if every one of its prefixes is also in the list — that is what "built one character at a time by other words" means. We want the longest such word, and the alphabetically smallest if there is a tie.
The trick is the sort order. We sort words by length descending, and for equal lengths alphabetically ascending. Then we just scan and return the first word that passes the buildable test — because of the sort, that first hit is automatically the longest and lex-smallest answer.
The test itself dumps all words into a set and checks that w[:1], w[:2], …, up to (but not including) the whole word are all present. If any prefix is missing, the word is rejected.
Example: ["w","wo","wor","worl","world"]. Sorted, world comes first. Its prefixes w, wo, wor, worl are all in the list, so it passes and we return "world".
The work is dominated by the sort plus checking prefixes, totaling about the combined length of all words.