Tries

Each node is a prefix; the word is the path, never stored. Constant in the number of words held.

Trigger in the prompt: 'Prefix', 'autocomplete', 'dictionary of words'.

mediumDesign Add and Search Words

A trie where search supports a wildcard matching any single character.

Trigger

A trie plus '.' or '?' wildcards.

Approach
  1. Insert is a plain trie insert.
  2. Search becomes a DFS: on a normal character, descend that one child; on a wildcard, try all.
  3. Bound the branching out loud: worst case O(26^k) for k wildcards.
Target complexity

Insert O(L). Search O(L) with no wildcards, up to O(26^L) in the pathological case.

Pitfall

Writing search iteratively and finding the wildcard branch impossible. Make it recursive.

Say it out loud

“Insert is a standard trie. Search stops being a walk and becomes a search: a concrete character descends one child, a wildcard forks into all of them. That's why I'll write it recursively — the branching is natural in the recursion and painful in a loop.”

Solve on LeetCode
mediumImplement Trie (Prefix Tree)

Build a prefix tree supporting insert, exact search and prefix search.

Trigger

The email names tries explicitly; also any 'autocomplete' or 'prefix' problem.

Approach
  1. Each node holds a dict of children plus an end-of-word flag.
  2. The word is not stored anywhere — it is the path from the root to a flagged node.
  3. insert walks and creates; search walks and checks the flag; starts_with walks and returns true.
  4. Say when a trie beats a hash set: prefixes, ordering, shared-prefix memory.
Target complexity

O(L) per operation, where L is the word length — independent of how many words are stored.

Pitfall

Returning true from `search` just because the path exists. You need the end-of-word flag.

Say it out loud

“Each node is a prefix and each edge is a character, so the word itself is never stored — it's the path. Every operation is O(length of the word), independent of how many words are in the trie, and that's the property a hash set can't give me for prefix queries.”

Solve on LeetCode