Trie

A trie (prefix tree) stores strings as paths through a tree of characters. It is ideal for prefix queries and fast pruning in word searches.

Pattern A: Core trie operations

Use when: you need insert, search, and prefix checks.

Invariant: each node represents a prefix; isWord marks full words.

Skeleton:

type Node struct { children[26]*Node; isWord bool }

Insert(word):
    cur = root
    for ch in word:
        if cur.children[idx] == nil: cur.children[idx] = new Node
        cur = cur.children[idx]
    cur.isWord = true

Search(word):
    cur = root
    for ch in word:
        if cur.children[idx] == nil: return false
        cur = cur.children[idx]
    return cur.isWord

StartsWith(prefix):
    ... same as Search but no isWord check

Problems:

• implement-trie-prefix-tree.

Pattern B: Wildcard search

Use when: '.' can match any letter.

Invariant: DFS explores all possible child branches for wildcards.

Skeleton:

func dfs(node, i):
    if i == len(word): return node.isWord
    ch = word[i]
    if ch != '.': return child exists and dfs(child, i+1)
    for each child: if dfs(child, i+1) return true
    return false

Problems:

• design-add-and-search-words-data-structure.

Pattern C: Trie + grid backtracking

Use when: you must find many words in a board efficiently.

Invariant: the current path is a prefix in the trie; if not, prune.

Skeleton:

build trie of words
for each cell:
    dfs(r,c, root)

func dfs(r,c,node):
    if out of bounds or visited: return
    ch = board[r][c]
    next = node.children[ch]
    if next == nil: return
    if next.isWord: record word, mark to avoid duplicates
    mark visited
    dfs neighbors with next
    unmark visited

Problems:

• word-search-ii.

Pattern D: Shortest prefix replacement

Use when: you replace words with the shortest root in a dictionary.

Invariant: the first isWord encountered is the shortest root.

Skeleton:

for word in sentence:
    cur = root
    for i, ch in word:
        if cur.children[idx] == nil: break
        cur = cur.children[idx]
        if cur.isWord: replace with word[:i+1]; break

Problems:

• replace-words.

When to use Tries (checklist)

• You need fast prefix checks or lexicon pruning.
• Many queries share prefixes.

Common failures (checklist)

• Forgetting to mark end-of-word nodes.
• Not pruning when a prefix does not exist.
• Returning duplicates in word search (mark found words).

Problem mapping

• implement-trie-prefix-tree: core operations.
• design-add-and-search-words-data-structure: wildcard DFS.
• word-search-ii: trie + grid backtracking.
• replace-words: shortest prefix replacement.