Pattern visualizer

Complete String

A word is 'complete' when every one of its prefixes was also inserted as its own word — not just present as trie nodes, but each marked END. Insert every word into a trie, then walk each word's path again: the moment an ancestor node's END flag is false, that word (and everything built on top of it) is disqualified, no matter how deep the trie goes. Animated on: words = ["a","ap","app","appl","apple","ba","bax"] — find the longest complete string..

The longest word whose every prefix is also a stored word

time O(n * L) to build and check every wordspace O(n * L)step 1 / 14

end

•

line 6

insert("a"): walk/create root -> a and mark "a" END. Any node already shared with an earlier word is reused, not duplicated.

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 isComplete(word):
8  cur <- root
9  FOR ch IN word:
10    cur <- cur.children[ch]
11    IF cur.end = false: RETURN false
12  RETURN true
13FUNCTION longestComplete(words): RETURN best w in words WHERE isComplete(w), by LENGTH desc THEN w asc

← / → step · space play · Home restart

Where to practice Trie

Practice Trie problems All Trie problems Back to roadmap