Medium Trie + BFS Tries
In plain English: Find the longest word where every prefix of that word is also in the list.
Insert all words into a trie, marking end-of-word nodes. BFS level by level — only explore children that are complete words themselves. The last complete word found at the deepest level (lexicographically smallest) is the answer.
Prompt
Given a list of words, return the longest word that can be built one character at a time by other words in the list. If tied, return the lexicographically smallest.
Try to write it from scratch before scrolling down.
Solution
from collections import deque
def longest_word(words):
# Build trie
root = {'#': ''} # '#' stores the word at this node
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node['#'] = w
# BFS: only follow paths where every prefix is a word
queue = deque([root])
best = ''
while queue:
node = queue.popleft()
for key in sorted(node.keys()):
if key == '#':
continue
child = node[key]
if '#' in child: # this prefix is a valid word
if len(child['#']) > len(best):
best = child['#']
queue.append(child)
return best
# Test: longest_word(["w","wo","wor","worl","world"]) == "world"
# Test: longest_word(["a","banana","app","appl","ap","apply","apple"])
# == "apple" (same length as "apply", but lexicographically smaller)