Longest Word in Dictionary

DFS only through END-marked children, tie-break lexicographically

time O(total characters)space O(total characters)

Insert every word into a trie and mark the node where each word ends. A word only qualifies if EVERY node on its path is an end node, not just its own final node — so a DFS from the root that refuses to step into any child that isn't marked END automatically skips every disqualified branch. Visiting children in sorted order makes the first word found at the longest length also the lexicographically smallest one.

Details

Animated on: Given words = ["a","ap","app","appl","apple","apply"], find the longest word buildable one character at a time where every prefix is also in the list. Break ties by returning the lexicographically smaller word.

Problem:Longest Word in DictionaryMedium

DFS only through END-marked children, tie-break lexicographically

step 1 / 15

•

Start with an empty trie holding just the root. Every word will be inserted one character at a time so shared prefixes share nodes.

Pseudocode

1FUNCTION insert(word):
2  cur <- root
3  FOR ch IN word:
4    IF ch NOT IN cur.children: cur.children[ch] <- new node
5    cur <- cur.children[ch]
6  cur.end <- true
7FUNCTION dfs(node, path):
8  IF LENGTH(path) > LENGTH(best): best <- path
9  ELSE IF LENGTH(path) = LENGTH(best) AND path < best: best <- path
10  FOR ch IN SORTED(node.children):
11    child <- node.children[ch]
12    IF child.end: dfs(child, path + ch)
13  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 15 steps

Start with an empty trie holding just the root. Every word will be inserted one character at a time so shared prefixes share nodes.
insert("a"): walk down creating any missing node for each character, then mark the final node END (double ring) — "a" is a complete dictionary word, not just a path.
insert("ap"): walk down creating any missing node for each character, then mark the final node END (double ring) — "ap" is a complete dictionary word, not just a path.
insert("app"): walk down creating any missing node for each character, then mark the final node END (double ring) — "app" is a complete dictionary word, not just a path.
insert("appl"): walk down creating any missing node for each character, then mark the final node END (double ring) — "appl" is a complete dictionary word, not just a path.
insert("apple"): walk down creating any missing node for each character, then mark the final node END (double ring) — "apple" is a complete dictionary word, not just a path.
insert("apply"): walk down creating any missing node for each character, then mark the final node END (double ring) — "apply" is a complete dictionary word, not just a path.
dfs starts at the root with an empty path and no best word yet.
Visit "a" (length 1) — longer than the current best "(none)", so best becomes "a".
Visit "ap" (length 2) — longer than the current best "a", so best becomes "ap".
Visit "app" (length 3) — longer than the current best "ap", so best becomes "app".
Visit "appl" (length 4) — longer than the current best "app", so best becomes "appl".
Visit "apple" (length 5) — longer than the current best "appl", so best becomes "apple".
Visit "apply" — same length as "apple" but lexicographically larger ("apply" > "apple"), so best stays "apple".
Every END-marked branch has been explored. The longest word whose every prefix is also a word is "apple".

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Word in Dictionary in the editor All Trie problems Back to roadmap