Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Concept

Overview

Prefix tree · shared prefixes stored once
step 1 / 25
trie
•
○ = node · ◎ ringed = end of a word
Concept
▸
1node = { children: map<char,node>, isWord }
2insert(word):
3    cur = root
4    for ch in word:
5        if ch not in cur.children:
6            cur.children[ch] = new node
7        cur = cur.children[ch]
8    cur.isWord = true
9 
10search(word): walk; true if path exists
11    AND the final node.isWord
12// shared prefixes ⇒ stored once
state
  • structureprefix tree

line 1A trie (prefix tree) stores a SET of strings by their letters. Each node is one character; a path down from the root spells a prefix. Ringed nodes mark where a complete word ends. Watch it grow.