LeetCode #212 Hard

Word Search II

Find which words from a list exist as adjacent-cell paths in a letter grid (no cell reused per word).

triebacktrackinggrid

02

Intuition

Running one grid-DFS per word repeats the same walks over and over. Instead put ALL words into a trie and run one DFS per grid cell, moving through grid and trie together: a step is only taken if the trie has that child, so the search dies the instant no word can match. Hitting a word-flag records a hit — the trie searches every word simultaneously.

How to spot this pattern

One trie walked alongside the grid DFS, instead of running Word Search once per word. The trie collapses shared prefixes so a dead end kills every word beneath it at once. Popping the "$" marker on a hit is a neat de-duplication trick — the word can never be reported twice.

03

Approach

1

Trie of all words

Insert every word; store the full word at its end node (no separate flag needed — the word itself is the flag).

2

DFS grid and trie in lockstep

From each cell whose letter is a trie child of the root: mark the cell visited, recurse into neighbors whose letters continue the trie path, unmark on return. Missing child = instant prune.

3

Dedupe and prune harder

On finding a word, null its marker so it is reported once. Optionally delete leaf trie nodes after exhausting them — the trie shrinks as words are found, speeding later cells.

04

Solution & live demo

▶1class Solution:
▶2    def findWords(self, board, words):
▶3        root = {}
▶4        for w in words:                       # build trie of all words
▶5            node = root
▶6            for ch in w: node = node.setdefault(ch, {})
▶7            node["$"] = w
▶8        R, C, res = len(board), len(board[0]), []
▶9        def dfs(r, c, node):
▶10            ch = board[r][c]
▶11            child = node.get(ch)
▶12            if not child: return
▶13            w = child.pop("$", None)
▶14            if w: res.append(w)               # found; popped so never re-added
▶15            board[r][c] = "#"                 # visited for this path
▶16            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
▶17                nr, nc = r+dr, c+dc
▶18                if 0 <= nr < R and 0 <= nc < C and board[nr][nc] != "#":
▶19                    dfs(nr, nc, child)
▶20            board[r][c] = ch                  # backtrack
▶21        for r in range(R):
▶22            for c in range(C):
▶23                dfs(r, c, root)
▶24        return res

05

Common pitfalls

Searching each word independently

✗ Wrong

for w in words:
    if exist(board, w): res.append(w)

✓ Right

# one trie, one DFS over the grid

With thousands of words sharing prefixes, that repeats the same failing exploration for every one of them. The trie makes the grid pay for each distinct prefix once, no matter how many words start with it.

Returning instead of continuing after a match

✗ Wrong

if w: res.append(w); return

✓ Right

if w: res.append(w)
# keep exploring

A matched word may be the prefix of a longer one also present in the grid. Returning at the first hit stops the walk and silently drops those longer words.

Forgetting to restore the cell

✗ Wrong

board[r][c] = "#"
for ...: dfs(...)

✓ Right

board[r][c] = "#"
for ...: dfs(...)
board[r][c] = ch

The # marks the cell as in-use for the current path only. Leaving it set makes the cell permanently unusable, so words needing it via a different route are never found.

06

Edge cases

Same word reachable two ways

Clearing the end-node marker on first find prevents duplicates.

One word is a prefix of another

Interior end-markers fire without stopping the deeper search.

Cell reuse within one word

Temporary '#' marking blocks revisits; restored on backtrack.

07

Complexity

Time

O(R·C·4^L)

Space

O(total chars)

L = longest word; trie pruning makes the practical cost far lower.