Where it runs
1. The problem
You type app into a search box, and a list drops down right away: apple, apply, application. This happens on every keystroke, over a dictionary of thousands of words, with no delay you can feel.
A plain set of words (a Set) answers "is apple in the list?" quickly: it uses the word's hash to go straight to the right place and doesn't look through the other words. It can't answer "does any word start with app?" that way. The set keeps each word separately, the shared beginnings of words are not linked in it at all, and you would have to check every word.
You want the question about the start of a word (the prefix) to be the fast one. Type three letters, get the answer, without looking through the whole dictionary.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedinsert("car"), insert("cat"), insert("dog"), search("cat"), search("ca"), search("cow")Store ["car", "cat", "dog"] so lookups go letter by letter. The root stands for the empty prefix.
Recognise it
Say these words and it is this pattern
- autocomplete or typeahead over many strings
- longest common prefix among words
- insert, search, and starts-with on a word set
- match against a large fixed dictionary by prefix
Looks similar, isn't
- Hash set / map
A map matches whole keys and nothing else. A trie also answers questions by prefix.
- Binary search tree
A search tree compares whole keys to choose a side. A trie walks one character at a time.
- Matrix word search (grid DFS/backtracking)
Searching a grid for many words uses a trie to prune. That page is the grid walk itself.
- DP on strings (word break)
Word break uses a trie to test each piece. The splitting decision lives in the table.
A word of length m costs O(m) to insert or find. Memory is O(total characters) over every word.
On LeetCode
Problems that store many words and ask about prefixes, such as whether a word or prefix exists, the shortest root that starts a word, or a search where a dot stands for any letter. Each character is one step down the trie, so a lookup costs the word's length.
The lesson task, word for word.
Insert every word, then walk down from the root while the node has exactly one child and no word ends there.
Insert the roots, then for each word walk down and stop at the first node that ends a root.
A dot matches any letter, so at a dot try every child of the node with a DFS.