PATTERN 20 OF 22

Tries

A trie (prefix tree) stores strings character-by-character in a tree structure, enabling O(m) insert, search, and prefix lookup where m is the word length. Master basic trie operations, wildcard DFS, and trie-accelerated grid search.

Time: O(m) per operation where m = word length

Space: O(n * m) where n = number of words, m = average length

Learn & Reference

Understanding the Pattern

Tries Pattern

Tries (pronounced "try", from retrieval) are tree structures where each node represents a character. A path from root to a marked node spells out a stored word. Unlike hash sets that treat words as opaque keys, tries expose the prefix structure of your dictionary.

Insert: apple, app, ape

        root
         |
         a
         |
         p
        / \
       p   e ✓
      / \
     l   ✓ (app)
     |
     e ✓ (apple)

The key insight: shared prefixes share nodes. Searching for any word starting with "ap" only traverses 2 nodes, regardless of dictionary size.

The TrieNode

Every trie implementation starts with the same building block:

TrieNode:
  children: map/array of child nodes (one per character)
  isEnd:    boolean — does a word end at this node?

Two common representations:

Array [26]: Fixed-size, O(1) lookup, best when input is lowercase English only
HashMap: Flexible, supports any character set (Unicode, mixed case)

Three Core Techniques

1. Basic Trie — Insert, Search, StartsWith

Insert: Walk the trie character by character. If a child doesn't exist, create it. Mark the last node as isEnd = true.

Search: Walk the trie. If any child is missing, return false. If you reach the end, check isEnd.

StartsWith: Same as search, but don't check isEnd — reaching the end of the prefix is enough.

insert("apple"):  root → a → p → p → l → e✓
search("apple"):  root → a → p → p → l → e✓ → isEnd? YES → true
search("app"):    root → a → p → p✗ → isEnd? NO → false
startsWith("app"): root → a → p → p → node exists → true

2. Trie + DFS (Wildcard Search)

When the search pattern contains wildcards (e.g., . matches any character), you can't follow a single path. Instead, at each wildcard, branch into all existing children via DFS.

search("b.d"):
  b → branch on '.' → try all children: a, then recurse
    a → d → isEnd? YES → true

Time complexity rises to O(26^k) in the worst case where k = number of wildcards, but it's fast in practice because most branches terminate quickly.

3. Trie + Backtracking (Grid Word Search)

For finding multiple words in a 2D grid, build a trie from the word list first. Then DFS from each cell, following the trie to prune branches early. This is dramatically faster than running a separate DFS for each word.

Build trie from ["oath", "eat"]
DFS from each cell, following trie nodes:
  cell 'o' → trie has 'o' child → continue
  cell 'a' → trie has 'a' child → continue
  cell 't' → trie has 't' child → continue
  cell 'h' → trie has 'h' child, isEnd → found "oath"!

Critical optimization: After finding a word, remove it from the trie (set isEnd = false or prune the node) to avoid collecting duplicates.

Common Mistakes

Forgetting isEnd — A prefix like "app" exists in the trie if "apple" was inserted, but search("app") should return false unless "app" was explicitly inserted. Always check isEnd.
Not handling wildcard . — When . appears, you must try ALL children, not skip the character. This requires DFS/recursion.
Off-by-one in trie depth — String index i corresponds to trie depth i+1 (root is depth 0, first character is depth 1).
Duplicate results in Word Search II — If the same word can be found via multiple grid paths, you'll add it multiple times. Remove or mark found words in the trie.
Array vs HashMap — Using children[26] when input includes uppercase or special characters causes index-out-of-bounds. Use a HashMap for arbitrary character sets.
Not pruning dead branches — In Word Search II, after finding a word, if a trie node has no remaining children, prune it to speed up future searches.

Template

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_end = False
5
6class Trie:
7    def __init__(self):
8        self.root = TrieNode()
9
10    def insert(self, word):
11        node = self.root
12        for char in word:
13            if char not in node.children:
14                node.children[char] = TrieNode()
15            node = node.children[char]
16        node.is_end = True
17
18    def search(self, word):
19        node = self.root
20        for char in word:
21            if char not in node.children:
22                return False
23            node = node.children[char]
24        return node.is_end
25
26    def starts_with(self, prefix):
27        node = self.root
28        for char in prefix:
29            if char not in node.children:
30                return False
31            node = node.children[char]
32        return True

{ }

Syntax Reference

1# --- TrieNode ---
2class TrieNode:
3    def __init__(self):
4        self.children = {}        # char -> TrieNode
5        self.is_end = False
6
7# --- Insert ---
8node = root
9for char in word:
10    if char not in node.children:
11        node.children[char] = TrieNode()
12    node = node.children[char]
13node.is_end = True
14
15# --- Search ---
16node = root
17for char in word:
18    if char not in node.children:
19        return False
20    node = node.children[char]
21return node.is_end
22
23# --- Starts With ---
24node = root
25for char in prefix:
26    if char not in node.children:
27        return False
28    node = node.children[char]
29return True  # Don't check is_end

📋

Common Recipes

1# Recipe 1: Basic Trie — Insert / Search / StartsWith
2class TrieNode:
3    def __init__(self):
4        self.children = {}
5        self.is_end = False
6
7class Trie:
8    def __init__(self):
9        self.root = TrieNode()
10
11    def insert(self, word):
12        node = self.root
13        for char in word:
14            if char not in node.children:
15                node.children[char] = TrieNode()
16            node = node.children[char]
17        node.is_end = True
18
19    def search(self, word):
20        node = self.root
21        for char in word:
22            if char not in node.children:
23                return False
24            node = node.children[char]
25        return node.is_end
26
27    def starts_with(self, prefix):
28        node = self.root
29        for char in prefix:
30            if char not in node.children:
31                return False
32            node = node.children[char]
33        return True
34
35# Recipe 2: Wildcard Search with DFS
36def search_with_wildcard(node, word, i):
37    if i == len(word):
38        return node.is_end
39    if word[i] == '.':
40        for child in node.children.values():
41            if search_with_wildcard(child, word, i + 1):
42                return True
43        return False
44    if word[i] not in node.children:
45        return False
46    return search_with_wildcard(node.children[word[i]], word, i + 1)
47
48# Recipe 3: Grid Word Search with Trie
49def find_words(board, words):
50    trie = Trie()
51    for w in words:
52        trie.insert(w)
53    result = []
54    def dfs(r, c, node, path):
55        if node.is_end:
56            result.append(path)
57            node.is_end = False  # Avoid duplicates
58        if r < 0 or r >= len(board) or c < 0 or c >= len(board[0]):
59            return
60        char = board[r][c]
61        if char not in node.children:
62            return
63        board[r][c] = '#'
64        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
65            dfs(r+dr, c+dc, node.children[char], path+char)
66        board[r][c] = char
67    for r in range(len(board)):
68        for c in range(len(board[0])):
69            dfs(r, c, trie.root, "")

O(n)

Complexity

Technique	Insert	Search	Space	Example
Basic Trie	O(m)	O(m)	O(n*m)	Implement Trie
Trie + DFS	O(m)	O(26^k * m)	O(n*m)	Add & Search Words
Trie + Backtracking	O(n*m)	O(RC4^L)	O(n*m)	Word Search II

Watch Out

✗Forgetting `isEnd` — A prefix like "app" exists in the trie if "apple" was inserted, but `search("app")` should return false unless "app" was explicitly inserted. Always check `isEnd`.
✗Not handling wildcard `.` — When `.` appears, you must try ALL children, not skip the character. This requires DFS/recursion.
✗Off-by-one in trie depth — String index `i` corresponds to trie depth `i+1` (root is depth 0, first character is depth 1).
✗Duplicate results in Word Search II — If the same word can be found via multiple grid paths, you'll add it multiple times. Remove or mark found words in the trie.
✗Array vs HashMap — Using `children[26]` when input includes uppercase or special characters causes index-out-of-bounds. Use a HashMap for arbitrary character sets.
✗Not pruning dead branches — In Word Search II, after finding a word, if a trie node has no remaining children, prune it to speed up future searches.

PRACTICE PROBLEMS

Graph Shortest Path

Design-Focused DSA