trie of 5 words
d
e
r
t
a
c
g
o
d
•
○ = node · ◎ ringed = end of a word
Brute force · scan every word
▸1given words[], prefix2result = []3for w in words:4 if w.startsWith(prefix): result.add(w)5return result
state
- prefix"car"
- words5
warming up the animation
Insert a set of words into a trie, then given a query prefix return all stored words that begin with that prefix, as in an autocomplete search.
▸1given words[], prefix2result = []3for w in words:4 if w.startsWith(prefix): result.add(w)5return result
line 1Autocomplete: list every stored word that begins with the prefix "car". Brute force: keep the words in a flat list and test each one's startsWith, including words that obviously can't match.