Introduction to Trie Pattern

You are given a dictionary of 100,000 words. As a user types, show every word that starts with what they have typed so far.

typed "ca"   suggests  cab, cable, cat, catch

Scanning the whole dictionary on every keystroke means 100,000 comparisons per letter. A hash set does not help either. It answers "is this exact word present" and knows nothing about prefixes.

Look at what the words share. cab, cable, cat and catch all begin with ca. Storing that prefix once, and hanging the rest off it, removes the repetition and answers the question directly.