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.

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

python

▶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

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.

06

Complexity

Time

O(R·C·4^L)

Space

O(total chars)

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