Longest Word in Dictionary
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"
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.