Trie patterns

The idea#

Picture a dictionary where every word is a path of letters, and words that start the same way share the pages until they split. "cat" and "car" share the page for "ca". You never store that shared opening twice.

A trie is a tree keyed by characters. A path from the root spells a prefix, and shared prefixes share nodes. Insert, search, and startsWith each walk O(L) steps for a word of length L. The space is proportional to the number of characters you stored times how you represent the alphabet.

Each node holds a map of children and a terminal flag, isEnd, that means a word ends here. "app" can be a word and also the prefix of "apple", so a node can be terminal and still have children. A counter on the node, bumped once for every word that passes through, answers "how many words start with this" in the same O(L) walk.

Deleting a word clears isEnd and then prunes. If a node is no longer terminal and has no children, it comes off its parent. "apple" can go away while "app" stays. Autocomplete walks to the prefix node and collects every terminal below it. That costs the length of the prefix plus the size of the subtree you read.

Why it matters#

Reach for a trie when the problem says prefix, autocomplete, starts with, or a dictionary you will query many times. A hash set answers "is this exact word present" in O(L) average, which matches a trie for a single lookup. The trie wins when the question is about the shared structure: every word with this prefix, the shortest root of this word, a wildcard dot that means any letter, a grid search that has to try many words at once.

Word search on a grid is the loud example. The dictionary goes in the trie, and each step on the board follows one child. A missing child kills the path. A dot in a search is the branch: one letter takes one child, and . tries every child, worst case O(26^dots · L). The cost lives in the wildcards.

You already use the shape when a phone suggests the rest of a contact after three letters. The contacts that share "Al" share those two nodes. The list under that node is the suggestion.

A small example#

function startsWith(words, prefix) {  const root = { kids: new Map(), end: false };  for (const word of words) {    let node = root;    for (const ch of word) {      if (!node.kids.has(ch)) node.kids.set(ch, { kids: new Map(), end: false });      node = node.kids.get(ch);    }    node.end = true;  }  let node = root;  for (const ch of prefix) {    node = node.kids.get(ch);    if (!node) return false;  }  return true;} const hasCat = startsWith(['cat', 'car', 'dog'], 'ca');

hasCat is true. "cat" and "car" share the nodes for c and a. The walk for "ca" never looks at "dog".

What the code below is doing#

Section 1 is TrieNode and Trie. Children are a Map. isEnd marks a word. count is how many inserted words pass through the node. insert, search, startsWith, and countPrefix are each a walk of length L. delete is recursive: it drops the count on the way down, clears isEnd at the end, and removes a child that is empty and not a word of its own. Deleting a missing word does nothing. Deleting "apple" leaves "app" in place.

Section 2 is autocomplete, wordsWithPrefix. Walk to the prefix. If it is missing, return an empty list. Otherwise depth-first collect every isEnd below, emitting a word before the longer words that extend it. Cost is O(prefix plus the size of that subtree).

Section 3 is word search II. Build a trie of the dictionary, then depth-first search the grid, stepping only into a child that matches the cell. A cell marked # is on the current path. On isEnd, record the word and clear the flag so a duplicate board path does not report it twice. The comment also names the optional prune of leaf nodes. Put the letter back on the way out. Worst case sits near O(m · n · 4 · 3^(L - 1)).

Section 4 builds the longest common prefix. Insert every word, then walk while the node has exactly one child and is not itself the end of a word. Stop when the words diverge or when one word ends. O(total characters). Section 5 replaces each word in a sentence with the shortest dictionary root that is a prefix of it. Walk until the first isEnd, and if the walk falls off the trie, keep the original word. O(total characters).

Section 6 is a dictionary that supports . as one wildcard character. addWord is a normal insert. search is a depth-first walk: a letter takes that child, a dot tries every child. Worst case O(26^dots · L). Section 7 is the prefix counter you already met on the node. Insert bumps count on every node the word passes through, and countPrefix reads that number in O(L).

Section 8 is the space note to say when someone asks. Map for any alphabet. A plain object for simple lowercase, with Object.create(null) so inherited keys stay out. Array(26) for speed and compactness on a through z, at the price of 26 slots on every node.

When you talk about it, say this: shared prefixes share nodes, and insert, search, and startsWith are O(L) in the length of the word.

Everything below is the demonstration. Same idea, written as code you can run.