Pattern Recognition Drill
Medium Tries
The Problem
Given a list of words, find the longest word that can be built one character at a time by other words in the list.
What approach would you use?
Think about it before scrolling down.
Insert all words. BFS/DFS on trie, only following nodes where end=True. Longest path wins. O(sum of lengths).
Sort words. Use a set; only add word if word[:-1] is in the set. O(n log n + sum of lengths).
Common Trap
Don't just find the longest word — every prefix of the answer must also be a word in the list.