Longest Word in Dictionary

Medium

Problem

Return the longest word in the list that can be built one letter at a time, where every prefix (its first 1, 2, … letters) is also in the list. Break ties by the lexicographically smallest word.

Example 1

Input:  ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"

"apply" is also buildable, but "apple" comes first alphabetically.

Test cases

Case 1

Input:    ["w","wo","wor","worl","world"]
Expected: "world"

Case 2

Input:    ["a","banana","app","appl","ap","apply","apple"]
Expected: "apple"

Case 3

Input:    ["b","a"]
Expected: "a"

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sort + set of buildable words

Time O(n log n · L)Space O(n · L)

Sort words (shorter first, then lexicographically). A word is buildable if its prefix without the last char is buildable.

function longestWord(words) {
words.sort();
const ok = new Set(['']);
let best = '';
for (const w of words) {
if (ok.has(w.slice(0, -1))) {
ok.add(w);
if (w.length > best.length) best = w;
}
}
return best;
}

Trie version: insert all, then DFS only through nodes that end a word; track the deepest, earliest-lexicographic one.