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.

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.