Pattern visualizer

Longest Word in Dictionary

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. 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..

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

time O(total characters)space O(total characters)step 1 / 15

•

line 1

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

Where to practice Trie

Practice Trie problems All Trie problems Back to roadmap