Longest Word in Dictionary
Implement longestWord
Given a list of
words, find the longest one that can be assembled letter by letter, where every intermediate prefix formed along the way is also present somewhere in the list. If several words tie for longest, return the alphabetically smallest of them; if no word qualifies at all, return an empty string.
A word only counts if literally every one of its prefixes, from length 1 up to its own full length, was separately inserted as its own word — a single missing link anywhere in that chain disqualifies it, no matter how long the word itself is. A trie makes that condition easy to check structurally: mark every node where some inserted word actually ends, then only ever walk into a child whose own node is marked that way. Any path the walk can complete is automatically an unbroken chain of real words, so no explicit prefix-by-prefix lookup is needed at all.
Example 1:
Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Example 2:
Input: words = ["a","banana","app","appl","ap","apply","apl"]
Output: "apply"
Example 3:
Input: words = ["ab","a","ac"]
Output: "ab"
+ 10 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ words.length ≤ 1000 - ●
1 ≤ words[i].length ≤ 30 - ●
words[i] consists of lowercase English letters - ●
words may contain duplicates
words =
["w", "wo", "wor", "worl", "world"]