Problem Statement

Longest Word in Dictionary

You are given a list of words. Your job is to find the longest word you can "grow" one letter at a time, where every smaller piece along the way is also a word in the list. Here is what that means: to build "apple", the list must contain "a", then "ap", then "app", then "appl", and finally "apple". Each step adds exactly one letter, and each step has to be a real word in the list. If two different words can both be built this way and they are the same length, return the one that comes first alphabetically. If no word can be built like this, return the empty string "".

mediumTrieTrieTime: O(n * m) · Space: O(n * m)

Signals to notice

longest word buildable one character at a timeeach prefix must also be a wordDFS on trie

Brute force first

Sort words, for each word check if all prefixes exist — with hash set. Works but doesn't exploit the structure. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Build a trie from all words. DFS the trie: only follow branches where isEnd is true at each step (each prefix must be a complete word). The deepest valid path is the longest word. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `words=["a","banana","app","appl","ap","apply","apple"]`

sort -> ["a","ap","app","appl","apple","apply","banana"]; valid={""}, result=""
word="a": prefix "" in valid -> add "a"; len 1>0 -> result="a"; valid={"","a"}
word="ap": prefix "a" in valid -> add "ap"; len 2>1 -> result="ap"
word="app": prefix "ap" in valid -> add "app"; len 3>2 -> result="app"
word="appl": prefix "app" in valid -> add "appl"; len 4>3 -> result="appl"
word="apple": prefix "appl" in valid -> add "apple"; len 5>4 -> result="apple"
word="apply": prefix "appl" in valid -> add "apply"; len 5 not >5 -> result stays "apple"
word="banana": prefix "banan" not in valid -> skip. return "apple"

What must stay true

A word is 'buildable' if every prefix of it is also in the dictionary. In the trie, this means every node along the path must be marked as a word end. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

sort(words)
valid = {""}; result = ""
for word in words:
    if word[:-1] in valid:
        valid.add(word)
        if len(word) > len(result): result = word
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not handling ties — when multiple words have the same length, return the lexicographically smallest. DFS with alphabetical child ordering naturally handles this. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Trie Pattern