Tries

Overview

A trie stores a set of strings as a tree, where each edge is a character and a path from the root marks the characters of a stored word. Insertion and lookup are O(L) where L is the word length, independent of how many words are stored. Tries are the right structure whenever you need to answer prefix questions cheaply.

Problems

208. Implement Trie (Prefix Tree) (Medium)
211. Design Add and Search Words Data Structure (Medium)
212. Word Search II (Hard)

Key patterns unlocked here

Canonical trie insert/search/startsWith, 208.
Wildcard search via trie DFS, 211 (backtrack on .).
Trie + grid DFS with trie-pruning, 212 (the hard payoff).