Word Search II (Trie + Backtrack)

▶

Steps

setup

Build Trie - insert 'eat'

Insert word 'eat' into the trie. Root → e(id=1) → a(id=2) → t(id=3, word='eat'). Three nodes created along the path.

💡 The trie stores all search words as paths from root. Each character gets its own node.

Line:

for w in words:
    node = root
    for c in w:
        if c not in node.children:
            node.children[c] = TrieNode()
        node = node.children[c]
    node.word = w

💡 Inserting 'eat' creates nodes for e→a→t with word='eat' at the leaf.

setup

Build Trie - insert 'oath'

Insert word 'oath'. Root → o(id=4) → a(id=5) → t(id=6) → h(id=7, word='oath'). Four nodes created.

💡 Notice 'oath' shares no prefix with 'eat' so a completely separate branch is created from root.

Line:

for c in w:
    if c not in node.children:
        node.children[c] = TrieNode()
    node = node.children[c]
node.word = w

💡 Root now has two children: e (for eat) and o (for oath). Each word occupies its own branch.

search

DFS from cell (1,1)='t' - no trie match, prune

Start DFS at board[1][1]='t'. Check if root has child 't' - it does not. Prune immediately without exploring neighbors.

💡 This is the power of the trie: if the first character doesn't match any word prefix we skip the entire DFS subtree from this cell.

Line:

def backtrack(r, c, node):
    letter = board[r][c]
    currNode = node.children.get(letter)
    if not currNode:
        return  # prune

💡 No word starts with 't' so this cell is useless as a starting point.

search

DFS from cell (1,3)='e' - match 'e', continue

Start DFS at board[1][3]='e'. Root has child 'e' (id=1). Mark board[1][3]='#', move to trie node e.

💡 'e' is the start of 'eat'. We mark the cell '#' to prevent revisiting it in the same DFS path.

Line:

board[r][c] = '#'
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
    nr, nc = r + dr, c + dc

💡 The cell is marked '#' as a visited guard. After backtracking it will be restored to 'e'.

search

DFS from (1,3)→(0,3)='a' - match 'a', continue

From board[1][3]='#' (was 'e'), check neighbor board[0][3]='a'. Trie node e has child 'a' (id=2). Mark board[0][3]='#', move to trie node a.

💡 We're building the word 'e→a'. The path so far on the board is (1,3)→(0,3).

Line:

currNode = node.children.get(letter)
if not currNode: return
board[r][c] = '#'

💡 The active_path now shows root→e→a. One more character needed to complete 'eat'.

search

DFS from (0,3)→(1,3) blocked - try (0,2)='a' - no 't'

(1,3) is '#' (already visited). Try neighbor (0,2)='a' - trie node 'a' has no child 'a'. Try (0,2)='a' is also not 't'. Need 't' but only neighbors are '#' or 'a'. No match on any side - backtrack.

💡 The board path e→a at (1,3)→(0,3) has no neighboring 't'. We must backtrack and restore both cells.

Line:

board[r][c] = letter  # restore after backtrack
if not currNode.children:
    node.children.pop(letter)  # prune trie

💡 Backtracking restores cells so other DFS paths can use them. This is the key backtracking step.

search

DFS from cell (1,3)='e' → neighbor (1,2)='a' → (1,1) was 't' - find 'eat'!

Restart from board[1][3]='e'. Move to neighbor (1,2)='a' (trie: e→a). From (1,2) move to neighbor (1,1)='t' (trie: a→t, word='eat'). Word found! Append 'eat' to result. Set currNode.word=None to prevent re-finding.

💡 This is the successful path: e(1,3) → a(1,2) → t(1,1). The trie guides us to recognize the complete word at t.

Line:

if currNode.word:
    result.append(currNode.word)
    currNode.word = None  # prevent duplicate

💡 Setting word=None on the found trie node ensures 'eat' is never added twice even if there's another path spelling it.

search

DFS from cell (0,0)='o' - match 'o', start 'oath' search

Scan all board cells for new starting characters. Cell (0,0)='o' matches root child 'o' (id=4). Mark board[0][0]='#', move to trie node o.

💡 We found the start of 'oath'. Now we need 'a' from a neighbor of (0,0).

Line:

for r in range(rows):
    for c in range(cols):
        backtrack(r, c, root)

💡 The full board scan ensures we try every possible starting position for words.

search

(0,0)→(1,0)='e' - no 'a' child for 'o' branch

From (0,0)='#', try neighbor (1,0)='e'. Trie node 'o' has no 'e' child. Try (0,1)='a' - trie node 'o' has 'a' child (id=5). Match! Move to (0,1).

💡 We skip (1,0) immediately because trie node 'o' has no 'e' child. The trie prunes bad directions instantly.

Line:

currNode = node.children.get(letter)
if not currNode:
    return

💡 Going right to (0,1)='a' matches the trie. Path: o(0,0)→a(0,1).

search

(0,1)→(1,1)='t' - match 't', one step closer

From (0,1)='a', check neighbors. (1,1)='t' - trie node 'a' (child of 'o') has 't' child (id=6). Match! Mark (1,1)='#', move to trie node t.

💡 Third character 't' found. Path so far: o(0,0)→a(0,1)→t(1,1). Need 'h' to complete 'oath'.

Line:

board[r][c] = '#'
backtrack(nr, nc, currNode)

💡 Three of four characters matched. One more hop to find 'h'.

search

(1,1)→(2,1)='h' - find 'oath'! Prune trie node

From (1,1)='t', check neighbor (2,1)='h'. Trie node 't' has 'h' child (id=7, word='oath'). Word found! Append 'oath' to result. Set word=None. Node 7 has no children → prune it from trie (pop 'h' from t's children).

💡 Found 'oath' via path (0,0)→(0,1)→(1,1)→(2,1). The trie prunes the leaf node immediately since it has no children and the word is consumed.

Line:

if currNode.word:
    result.append(currNode.word)
    currNode.word = None
...
if not currNode.children:
    node.children.pop(letter)

💡 Pruning the empty leaf makes the trie smaller and future searches faster. If no words share the 'o→a→t→h' prefix, the entire branch can disappear.

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

class Solution:
    def buildTrie(self, words):
        root = TrieNode()
        for w in words:
            node = root
            for c in w:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.word = w
        return root

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = self.buildTrie(words)
        rows, cols = len(board), len(board[0])
        result = []

        def backtrack(r, c, node):
            letter = board[r][c]
            currNode = node.children.get(letter)
            if not currNode:
                return
            if currNode.word:
                result.append(currNode.word)
                currNode.word = None

            board[r][c] = '#'
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                    backtrack(nr, nc, currNode)
            board[r][c] = letter

            if not currNode.children:
                node.children.pop(letter)

        for r in range(rows):
            for c in range(cols):
                backtrack(r, c, root)

        return result

# Driver code
if __name__ == '__main__':
    board = [
        ['o','a','a','n'],
        ['e','t','a','e'],
        ['i','h','k','r'],
        ['i','f','l','v']
    ]
    words = ['oath','pea','eat','rain']
    sol = Solution()
    print(sol.findWords(board, words))

📊

Word Search II - Watch the Trie + Backtracking Execute, Step by Step

The trie acts as a combined dictionary and prefix checker - instead of checking all words per cell, we follow one trie path that matches the board. When the trie has no child for a board character we prune immediately.

insert

eat

◉eat*

insert

oath

◉eoath*

search

t

◉

Search: false

search

e

◉e

search

ea

◉ea

search

e

◉e

search

eat

◉eat*

Pairs found: 1

Search: true

search

o

◉o

Pairs found: 1

search

oa

◉oa

Pairs found: 1

search

oat

◉oat

Pairs found: 1

find_pairs

oath

◉oh*

Pairs found: 2

Search: true

Key Takeaways

✓ Building a trie from all words allows prefix-based pruning - if no word starts with a board character the DFS is skipped entirely.

Without a trie you'd check each word against each board path separately, which is much slower.

✓ Marking cells '#' during DFS prevents revisiting the same cell in one path, ensuring valid board paths only.

The restore step (board[r][c] = letter) after backtracking lets other DFS paths reuse the cell.

✓ Pruning trie nodes with no children after finding a word avoids re-finding the same word and shrinks future search space.

This optimization is subtle but powerful - the trie gets smaller as words are found.