Tries
How do many words share their prefixes?
Two million names per keystroke
A payments app wants merchant search: type a few letters, and matching shops appear under the box. The catalogue has 2 million merchant names, and they already sit in a hash set, which is how the app checks that a merchant exists.
For suggestions the set has nothing to offer. "Is cha a merchant?" No. So the endpoint loops over all 2 million names on every keystroke and keeps the ones that start with what was typed. In the load test each keystroke takes 140 ms of CPU. At the morning peak the test sends 3,000 keystrokes a second. Do the sum: 3,000 × 140 ms is 420 seconds of work arriving every second. The servers fall over in four minutes.
Look at the matches for cha: Chaat Junction, Chai Katte, Chandra Medicals, Chawla Electricals. Thousands of names share those three letters, and the loop reads the same three letters again for each of the 2 million names, on every keystroke. A phone's contacts app answers the same question instantly.
Pause and predict What could the search store once, so that typing one more letter costs one step, however many names there are?
A node is a prefix
A hash set answers "is this a word?" in O(L), where L is the length of the word. Ask it "does any word start with car?" and it cannot help: you would have to test every word.
Words that start the same way share their first letters. A trie stores those letters once. It is a tree whose edges are letters, so every node stands for the string spelled on the path from the root: a prefix.
Pause and predict Only card has been inserted. Does search("car") return true?
When a letter can be anything
Design Add and Search Words adds the character ., which matches any single letter. A normal letter still has one edge to follow. At a dot, every existing child is a candidate, so the search tries them one by one and stops at the first that succeeds. That is a depth-first search.
Pause and predict The pattern is three dots, ..., and no word fits it. How much of the trie does the search visit?
Many words, one grid
Word Search in Unit 12 traces one word in a grid with a DFS. Word Search II hands you thousands of words. Running Word Search once per word walks the path for sto once for stone, again for stole, again for stoned.
Put the words in a trie instead, and walk the grid and the trie together. The DFS steps onto a neighbour only if its letter is a child of the current trie node. A path stops at the first letter that no word continues with, and it stops for all the words at once. Store each word at its end node, so that reporting it when you reach that node costs nothing extra.
Then prune, because the trie should hold only the words still worth looking for. Clear a word when you find it, so it is reported once. Remove a child once nothing is left below it, so later searches stop sooner.
Pause and predict The grid is 4 by 4 and every cell holds the letter a. None of the words in the list appear in it. Does removing found words from the trie make the search faster?
Back to the search box
The merchant search is a trie whose nodes also keep their few best completions, so each keystroke is one edge and one read. Ranking those completions, keeping them fresh and serving them to millions of phones is a system design question, and the design course builds exactly that service.
How to recognise it
The signal is a question about the prefixes of many strings, asked many times. A wildcard that stands for any one letter is the same signal, solved with a DFS. Searching for many words together in one structure is the hardest version.
Pause and predict The only question ever asked is "was card inserted?". Do you need a trie?
The ones that only look like it
- Checking exact membership only: use a set, from hashing. Grouping anagrams uses a map from each word's letter signature.
- One word in a grid: plain backtracking. A trie is worth it only when many words share the walk.
- Prefix queries on a list that never changes: sorting plus a binary search often does it with less code, because all the words with a given prefix form one unbroken block of a sorted list.
Where it bites
Pause and predict A Java grid DFS marks a cell as in use by writing '#' into it. Later it reads that cell and looks up next['#' - 'a']. What happens?
- Searching without the end flag. Reaching the node only shows that some word passes through it. Insert
card, andsearch("car")would wrongly return true. - Creating a child that already exists.
next[c] = new Node()without the null check replaces the existing child and loses every word below it. - Stopping the dot search at the first child. Return true on the first success, but return false only after every child has failed.
- Not removing found words in Word Search II. A word is then reported once for every place it can be traced, and the DFS keeps walking branches with nothing left to find.
- Stopping the grid DFS at a found word. A longer word may continue from the same node, as
stonedcontinuesstone.