Store words by their letters, not as whole strings, and shared PREFIXES share the same path — ‘car’, ‘card’, and ‘care’ all walk the same first three steps, then branch. That’s a trie (prefix tree). Looking up a word or ALL words with a prefix is proportional to its length, not the dictionary size — which is exactly how autocomplete works. Slide to grow the prefix and light the branch.
A trie (prefix tree) stores strings by their characters: each edge is a letter and each path from the root spells a prefix, with word-ends marked. Common prefixes are stored ONCE and shared, so lookup, insert, and prefix queries cost O(length of the key) — independent of how many words are stored. It enumerates all words under a prefix by walking that subtree, which is exactly autocomplete / typeahead; it also powers spell-checkers, IP routing tables, and dictionary compression. A fail-loud self-check throws unless exact and prefix lookups agree with the stored words. ◆ real data structures, node-verified.
Tries trade memory for speed — many sparse nodes; compressed (radix) tries and DAWGs reduce that. The O(length) prefix cost and shared-prefix structure are exact.