Tries

A trie stores strings by shared prefixes. Each edge consumes one character, so lookup cost depends on word length rather than the number of stored words. The key distinction is whether the current node is merely a prefix or a completed word.

Typical node fields: children: Map<char, TrieNode> (or fixed array for a-z) plus isWord or wordCount. Walking cat is three pointer hops; words that share ca... reuse the same first edges. Board DFS + trie pruning works because early missing edges cut entire subtrees that string matching would naïvely explore.

Quick Identifier

• Topic: tries
• Pattern: Prefix tree, wildcard DFS, trie-backed backtracking, or autocomplete.
• Core Question: Does sharing prefixes avoid repeated scans over the dictionary?

Quick Sights

• Typical Time Complexity: O(L) per direct operation, where L is word or prefix length.
• Typical Space Complexity: Proportional to total stored characters, after prefix sharing.
• Core Mechanism: Walk character by character from the root; branch only when wildcard or board search requires it.

Diagram

Recognition Cues

• Prefix, dictionary, autocomplete, replace words, wildcard . search.
• Word search on a board with many dictionary words.
• Need many prefix queries faster than scanning every word.

Problem List

Start with 208. Implement Trie, then 211. Design Add and Search Words, 648. Replace Words, 1268. Search Suggestions System, and 212. Word Search II.