pattern heroPT–23LeetCode Extension

Trie (prefix tree)

Store words as a tree of letters: words with the same start share a path. Finding a word or a prefix takes as many steps as it has letters, however many words are stored.

Variant
P17 Trie (prefix tree)Insert and search · 1×

Example problem: insert the words "sun", "sum", "so", then ask whether "su" is a word, whether some word starts with "su", and whether some word starts with "b".

rootinsert("sun")sun
in the trie; a double ring ends a wordjust addedthe path so farcurrent nodefoundmissing letter

Insert "sun": start at the root

word = "sun"ch = –node = rootisPrefix = –
01/58
restart · back · play · step
Speed
1function insert(word):
2 node = root
3 for each ch in word:
4 if ch not in node.children:
5 node.children[ch] = new node
6 node = node.children[ch]
7 node.end = true
8function search(word, isPrefix):
9 node = root
10 for each ch in word:
11 if ch not in node.children:
12 return false
13 node = node.children[ch]
14 return isPrefix or node.end

← → step · space play/pause

How to recognise

many words and questions about their starts: does a word or prefix exist, autocomplete, a word with wildcard letters, or many words to find in one grid.

How to solve problems like this

  1. Make a node type: children by letter (a map or an array of 26) and an end flag.
  2. Insert: walk from the root, add a missing child for each letter, mark the last node as an end.
  3. Search: walk the same way and stop at a missing letter. A word needs the end mark, a prefix does not.
  4. For many words in a grid, walk the trie and the grid together, so every prefix that leads nowhere stops the search early.

Variant: Search with .

The same, but the pattern has a "." that stands for any letter. A normal letter leads down one branch, a dot down all of them, so at a dot each branch is tried in turn.

  1. Write match(node, i): does the rest of the pattern from i fit below this node?
  2. Base case: at the end of the pattern, the node must carry the end mark.
  3. A plain letter: go to that one child, or return false if it is missing.
  4. A wildcard: call match on every child and return true as soon as one of them does.

Where it's used

  • Routing. The Linux kernel decides where to send a packet using a trie of IP addresses (fib_trie): it walks down the bits of the address and finds the longest matching prefix.
  • Web frameworks. The Go routers httprouter and Gin keep page paths such as /users/:id in a prefix tree, so the right handler is found in as many steps as the path is long, however many routes there are.
  • Redis. Redis stores its Streams in a compressed prefix tree called rax.