Sign in to watch this lesson
Algorithms - Strings · 4:52
Tries
A trie stores a set of words as a tree of letters, so shared prefixes are kept once and "how many words start with p?" costs one step per letter of p, however many words there are. We build one from six words, add pass counters for prefix counts and deletion, lay it out as an array of child indices to see its O(m·k) memory, time it against scanning every symbol on a Mac, and finish with the binary trie that finds the maximum XOR pair.
You will learn
- Build a trie as an array of vertices with child indices, inserting a word in O(|s|) and marking the vertices where words end
- Answer prefix-count queries in O(|p|) with per-vertex pass counters, and delete words by decrementing them
- Reason about the O(m·k) memory of the array layout and when to switch to a map or sorted children
- Use a binary trie with a greedy opposite-bit walk to find maximum XOR pairs, including in a sliding window