DSA problem
Longest Word in Dictionary
Given an array of strings words representing an English dictionary, return the longest word in words that can be built one character at a time by repeatedly appending a single letter to a shorter word already in the dictionary. If there are multiple possible answers, return the lexicographically smallest one. If no such word exists, return the empty string.
The key insight is the recursive nature of the buildability rule: a word w of length L is buildable if and only if its prefix w[0..L-1] (of length L-1) is also in the dictionary and is itself buildable. The base case is the empty string, which is buildable by definition.
A trie matches this structure beautifully. Insert every word into a trie. Then traverse the trie with BFS or DFS, descending only into children whose isEnd flag is true — meaning the prefix represented by that node is itself an inserted word. Among all reachable end-of-word nodes, keep the one whose path produces the longest string, breaking ties by choosing the lexicographically smaller string.
Iterating children in alphabetical order makes the lexicographic tie-break automatic for DFS: among words of equal depth, the first one discovered is alphabetically smallest. Each character contributes a constant-time check, so the overall complexity is O(total characters across all words) in time and the trie storage is O(total characters) in space.
Examples
words = ["w","wo","wor","worl","world"]"world"words = ["a","banana","app","appl","ap","apply","apple"]"apple"words = ["yo","ew","fc","zrc","yodn","fcm","qm","qmo","fcmz","z","ewq","yod","ewqz","y"]"yodn"Constraints
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 30
- All the strings of words consist of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.