Longest Word in Dictionary
Module 20 · Tries
Problem
Given an array of strings words, find the longest word that can be
"built" one character at a time by other words in words — meaning
every proper prefix of the word is also present in words. If there
are ties for longest, return the lexicographically smallest one. If no
word qualifies, return the empty string. (LeetCode 720.)
Examples
Example 1
words = ["w","wo","wor","worl","world"]Output"world"Explanation. every prefix — w, wo, wor, worl — is also in words
Example 2
words = ["a","banana","app","appl","ap","apply","apple"]Output"apple"Explanation. a, ap, app, appl, apple all present; "apply" also qualifies at length 5, but "apple" < "apply" lexically
Constraints
1 ≤ words.length ≤ 1000,1 ≤ words[i].length ≤ 30, lowercase letters only.
Attempt it first
This problem reuses the trie's is_end_of_word flag as the entire
constraint check — "every proper prefix is also a complete word" is
literally "every node on the path to this word, except possibly the
word's own final node, has is_end_of_word = True." Before opening
anything, think about how you'd walk the trie to find the longest such
"fully-buildable" path, and how you'd break ties toward the
lexicographically smallest word without sorting the whole input first.