212. Word Search II

Quick Identifier

Topic: tries
Pattern: Trie + DFS / Backtracking
Difficulty: Hard
Companies: Amazon, Google, Meta, Microsoft, Airbnb
Frequency: Very High
LeetCode: 212

Quick Sights

Time Complexity: O(rows · cols · 4^L) from the optimal approach.
Space Complexity: O(total stored characters) across inserted words; each single operation walks O(L) nodes.
Core Mechanism: Given a 2D grid of characters and a list of words, return all words that can be formed by moving up/down/left/right on the grid using each cell at most once per path (per word search). Words are unique in the result set.

Given a 2D grid of characters and a list of words, return all words that can be formed by moving up/down/left/right on the grid using each cell at most once per path (per word search). Words are unique in the result set.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

Many query words on same board — pure per-word backtrack from 79 would repeat work
Prefix sharing — trie over words + prune DFS when path is not a prefix
On visit, mark cell; on backtrack, unmark

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — run single-word grid DFS for every query word independently — repeats board exploration; blows up when word count is large.
Acceptable — build trie; DFS without pruning matched subtrees — still faster than brute but revisits redundant prefixes.
Optimal — shared trie over all words; DFS only follows edges that exist; clear matched terminal string (or remove subtree) to avoid duplicate reporting — O(rows · cols · 4^L) worst-case traversal bound with strong early exits in practice (L = max word length).

Optimal Solution

Go

type TrieNode struct {
	children   [26]*TrieNode
	word       string
}

func findWords(board [][]byte, words []string) []string {
	root := &TrieNode{}
	for _, word := range words {
		node := root
		for index := 0; index < len(word); index++ {
			charIndex := int(word[index] - 'a')
			if node.children[charIndex] == nil {
				node.children[charIndex] = &TrieNode{}
			}
			node = node.children[charIndex]
		}
		node.word = word
	}

	rows := len(board)
	cols := len(board[0])
	seen := make([][]bool, rows)
	for row := range seen {
		seen[row] = make([]bool, cols)
	}
	output := []string{}

	var explore func(row int, col int, node *TrieNode)
	explore = func(row int, col int, node *TrieNode) {
		if row < 0 || col < 0 || row >= rows || col >= cols || seen[row][col] {
			return
		}
		charIndex := int(board[row][col] - 'a')
		if node.children[charIndex] == nil {
			return
		}
		next := node.children[charIndex]
		if next.word != "" {
			output = append(output, next.word)
			next.word = ""
		}
		seen[row][col] = true
		explore(row+1, col, next)
		explore(row-1, col, next)
		explore(row, col+1, next)
		explore(row, col-1, next)
		seen[row][col] = false
	}

	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			explore(row, col, root)
		}
	}
	return output
}

JavaScript

class TrieNode {
	constructor() {
		this.children = new Array(26).fill(null);
		this.word = null;
	}
}

function findWords(board, words) {
	const root = new TrieNode();
	for (const word of words) {
		let node = root;
		for (let index = 0; index < word.length; index++) {
			const charIndex = word.charCodeAt(index) - 97;
			if (node.children[charIndex] === null) {
				node.children[charIndex] = new TrieNode();
			}
			node = node.children[charIndex];
		}
		node.word = word;
	}
	const rows = board.length;
	const cols = board[0].length;
	const output = [];
	const seen = Array.from({ length: rows }, () => Array(cols).fill(false));

	function explore(row, col, node) {
		if (row < 0 || col < 0 || row >= rows || col >= cols || seen[row][col]) {
			return;
		}
		const charIndex = board[row].charCodeAt(col) - 97;
		const next = node.children[charIndex];
		if (next === null) {
			return;
		}
		if (next.word !== null) {
			output.push(next.word);
			next.word = null;
		}
		seen[row][col] = true;
		explore(row + 1, col, next);
		explore(row - 1, col, next);
		explore(row, col + 1, next);
		explore(row, col - 1, next);
		seen[row][col] = false;
	}

	for (let row = 0; row < rows; row++) {
		for (let col = 0; col < cols; col++) {
			explore(row, col, root);
		}
	}
	return output;
}

Walkthrough

Insert oath, eta, eat into trie. From each cell, walk only if the next character exists in the current trie level; when a node has word set, record and clear to avoid duplicates.

Invariant: DFS never descends a path that is not a trie prefix, so we avoid most of the blind 79-style exploration.

Edge Cases

Overlapping letters used in different words — seen is per path; backtrack clears
Word length 1
Board smaller than all words
Same word in words list twice — result should list once (trie end node stores one string)

Pitfalls

Not pruning trie after match — can still be OK; clearing word helps
Reusing board in place for marks without restore — prefer seen or flip char with restore
JavaScript: charCodeAt vs code point for non-a..z (problem is lowercase English)

Variants

Count matches with repetition in word list — store count at trie leaf.
3D board or 8-connected — neighbor loops change only.
Immutable board + bitmask visited — bitmask for tiny boards.

Mind-Map Tags

#trie #backtracking #word-search #prune #grid-dfs #hard-classic #prefix-tree