LeetCode 212 - Word Search II

LeetCode 212, LeetCode Word Search II, asks us to find every word from a given dictionary that can be formed inside a 2D character grid. Each word must be built by moving one cell at a time horizontally or vertically.

leetcodehardarraystringbacktrackingtriematrix

LeetCode Problem 212

Difficulty: 🔴 Hard
Topics: Array, String, Backtracking, Trie, Matrix

Solution

Problem Understanding

LeetCode 212, LeetCode Word Search II, asks us to find every word from a given dictionary that can be formed inside a 2D character grid. Each word must be built by moving one cell at a time horizontally or vertically. Diagonal movement is not allowed, and a board cell cannot be reused within the same word construction.

The input consists of two parts. The first is an m x n matrix called board, where every cell contains a lowercase English letter. The second is a list of candidate strings called words. The task is to return every word that can actually be formed on the board according to the movement rules.

The important detail is that we are not searching for a single word. We may need to search for up to 3 * 10^4 words, and each word may have length up to 10. The board itself can be as large as 12 x 12, which means there can be up to 144 starting positions.

A naive implementation that independently searches for every word quickly becomes too expensive. If we performed a full DFS for each word separately, we would repeatedly traverse the same prefixes across the board. The key challenge is avoiding duplicated work.

Several edge cases are important:

  • Multiple words may share prefixes such as "eat" and "eater", so prefix reuse becomes critical for efficiency.
  • The same cell cannot be revisited during one DFS path, which means we must carefully manage visited state.
  • Some words may not exist at all, and the algorithm must terminate efficiently without exploring unnecessary paths.
  • A board may contain many repeated characters, causing naive backtracking to explode combinatorially.
  • The problem guarantees all words are unique, which simplifies duplicate handling slightly, though the same word may still be discoverable from multiple paths.

Approaches

Brute Force Approach

The brute-force solution searches for every word independently. For each word, we iterate through every board cell and launch a DFS whenever the first character matches. During DFS, we recursively explore neighboring cells while checking whether the current path still matches the target word.

This works because DFS explores all valid paths that could construct the word. If any path matches the entire word, the word exists in the board.

However, this approach performs massive duplicated work. Suppose the dictionary contains many words sharing prefixes like "oa", "oat", and "oath". The brute-force method repeatedly traverses the same board paths separately for each word.

The complexity becomes prohibitively large under the given constraints. With up to 30,000 words, repeated DFS traversals are far too expensive.

Optimal Approach

The key insight is that many words share common prefixes. Instead of searching each word independently, we can build a Trie, also called a prefix tree, containing all words.

A Trie allows us to explore the board and dictionary simultaneously. As we perform DFS on the board, we walk through Trie nodes at the same time. The moment a path no longer matches any Trie prefix, we stop exploring immediately.

This pruning is extremely powerful. Instead of exploring every possible path for every word, we only explore paths that correspond to at least one valid dictionary prefix.

The algorithm combines:

  • Trie for efficient prefix matching
  • DFS backtracking for board traversal
  • In-place visited marking to avoid extra memory overhead

This reduces redundant work dramatically and makes the solution feasible for the constraint limits.

Approach Time Complexity Space Complexity Notes
Brute Force O(W × M × N × 4^L) O(L) Searches every word independently
Optimal O(M × N × 4^L + totalWordsLength) O(totalWordsLength) Trie enables prefix pruning

Where:

  • W = number of words
  • M × N = board size
  • L = maximum word length

Algorithm Walkthrough

  1. Build a Trie containing all words.

Each Trie node stores:

  • Child pointers for next characters
  • An optional complete word marker

We use a Trie because it efficiently represents shared prefixes. If many words begin with the same characters, they share the same Trie path. 2. Insert every word into the Trie.

While inserting characters, create child nodes as needed. At the final node of each word, store the full word itself.

Storing the complete word at terminal nodes avoids rebuilding strings during DFS. 3. Start DFS from every board cell.

Every cell could potentially begin a valid word, so we launch DFS from each position. 4. During DFS, check whether the current board character exists in the Trie node.

If the character is not a valid child, stop immediately. This pruning prevents unnecessary exploration. 5. Advance into the Trie.

Move from the current Trie node to the child node corresponding to the board character. 6. Check whether the Trie node completes a word.

If the node contains a stored word, add it to the result set.

To avoid duplicates, clear the stored word after discovery. 7. Mark the current board cell as visited.

We temporarily replace the character with a sentinel value such as "#".

This prevents revisiting the same cell during the current DFS path. 8. Explore all four directions.

Recursively search:

  • Up
  • Down
  • Left
  • Right
  1. Restore the board cell after DFS returns.

This backtracking step ensures other DFS paths can reuse the cell later. 10. Optionally prune empty Trie branches.

If a Trie node has no remaining children after exploration, remove it from the parent. This optimization reduces future DFS work.

Why it works

The algorithm maintains the invariant that every DFS path corresponds exactly to a valid Trie prefix. Therefore, DFS never explores impossible word prefixes. Since every valid board path is explored whenever its prefix exists in the Trie, all constructible words are eventually found. Backtracking guarantees cells are never reused within the same path while still remaining available for future searches.

Python Solution

from typing import List

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

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()

        # Build Trie
        for word in words:
            node = root

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

                node = node.children[char]

            node.word = word

        rows = len(board)
        cols = len(board[0])

        result = []

        def dfs(row: int, col: int, parent: TrieNode) -> None:
            char = board[row][col]

            if char not in parent.children:
                return

            node = parent.children[char]

            # Found a complete word
            if node.word is not None:
                result.append(node.word)
                node.word = None

            # Mark visited
            board[row][col] = "#"

            directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc

                if (
                    0 <= new_row < rows
                    and 0 <= new_col < cols
                    and board[new_row][new_col] != "#"
                ):
                    dfs(new_row, new_col, node)

            # Restore board
            board[row][col] = char

            # Trie pruning optimization
            if not node.children and node.word is None:
                del parent.children[char]

        for row in range(rows):
            for col in range(cols):
                dfs(row, col, root)

        return result

The implementation begins by defining a TrieNode class. Each node contains a dictionary of children and an optional stored word. The stored word exists only at terminal nodes.

The Trie construction phase inserts every dictionary word character by character. Shared prefixes naturally reuse existing Trie nodes.

The DFS function performs the main search. It first checks whether the current board character exists in the current Trie node. If not, the search stops immediately because no dictionary word can continue from this path.

When a Trie node contains a complete word, the word is appended to the result list. The word is then set to None so duplicate discoveries are avoided.

Visited tracking is handled by temporarily replacing the board character with "#". This avoids allocating a separate visited matrix and keeps space usage efficient.

After recursively exploring neighboring cells, the original board character is restored. This is the classic backtracking step.

Finally, the Trie pruning optimization removes exhausted branches. Once a Trie node no longer contains children or words, it becomes unnecessary and can be deleted to reduce future DFS work.

Go Solution

package main

type TrieNode struct {
	children map[byte]*TrieNode
	word     string
}

func newTrieNode() *TrieNode {
	return &TrieNode{
		children: make(map[byte]*TrieNode),
	}
}

func findWords(board [][]byte, words []string) []string {
	root := newTrieNode()

	// Build Trie
	for _, word := range words {
		node := root

		for i := 0; i < len(word); i++ {
			char := word[i]

			if _, exists := node.children[char]; !exists {
				node.children[char] = newTrieNode()
			}

			node = node.children[char]
		}

		node.word = word
	}

	rows := len(board)
	cols := len(board[0])

	result := []string{}

	var dfs func(int, int, *TrieNode)

	dfs = func(row int, col int, parent *TrieNode) {
		char := board[row][col]

		node, exists := parent.children[char]
		if !exists {
			return
		}

		// Found a word
		if node.word != "" {
			result = append(result, node.word)
			node.word = ""
		}

		// Mark visited
		board[row][col] = '#'

		directions := [][2]int{
			{1, 0},
			{-1, 0},
			{0, 1},
			{0, -1},
		}

		for _, dir := range directions {
			newRow := row + dir[0]
			newCol := col + dir[1]

			if newRow >= 0 &&
				newRow < rows &&
				newCol >= 0 &&
				newCol < cols &&
				board[newRow][newCol] != '#' {

				dfs(newRow, newCol, node)
			}
		}

		// Restore board
		board[row][col] = char

		// Trie pruning
		if len(node.children) == 0 && node.word == "" {
			delete(parent.children, char)
		}
	}

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

	return result
}

The Go implementation mirrors the Python logic closely, but several language-specific differences are worth noting.

Go does not have Python dictionaries with implicit insertion semantics, so we explicitly check whether child nodes exist before creating them.

Strings in Go are immutable, but indexing by byte is efficient because the input contains only lowercase English letters.

Instead of using None to indicate absence of a stored word, Go uses the empty string "".

The DFS function is implemented as a closure so it can naturally access shared variables like result, rows, and cols.

Worked Examples

Example 1

Input:

board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

words = ["oath","pea","eat","rain"]

Trie Structure

Prefix Exists
o Yes
oa Yes
oat Yes
oath Yes
p Yes
pe Yes
pea Yes
e Yes
ea Yes
eat Yes
r Yes
ra Yes
rai Yes
rain Yes

DFS Trace for "oath"

Step Position Character Current Prefix
1 (0,0) o o
2 (0,1) a oa
3 (1,1) t oat
4 (2,1) h oath

At this point, the Trie node contains "oath", so it is added to the result.

DFS Trace for "eat"

Step Position Character Current Prefix
1 (1,3) e e
2 (1,2) a ea
3 (1,1) t eat

The word "eat" is found and added.

Final Result

["oath", "eat"]

Example 2

Input:

board =
[
  ['a','b'],
  ['c','d']
]

words = ["abcb"]

DFS Exploration

Path Status
a → b Valid
a → b → c Invalid adjacency
a → b → c → b Would require reusing cell

Since cells cannot be reused, the word cannot be formed.

Final result:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(M × N × 4^L + totalWordsLength) DFS explores valid Trie-guided paths only
Space O(totalWordsLength) Trie storage dominates auxiliary memory

The Trie construction requires inserting every character from every word exactly once, giving O(totalWordsLength) preprocessing time and space.

The DFS complexity is bounded by the number of board cells times the branching factor of recursive exploration. In practice, Trie pruning dramatically reduces exploration compared to brute force because invalid prefixes terminate immediately.

The recursion stack depth is at most the maximum word length, which is only 10.

Test Cases

from typing import List

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

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()

        for word in words:
            node = root

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

                node = node.children[char]

            node.word = word

        rows = len(board)
        cols = len(board[0])

        result = []

        def dfs(row, col, parent):
            char = board[row][col]

            if char not in parent.children:
                return

            node = parent.children[char]

            if node.word:
                result.append(node.word)
                node.word = None

            board[row][col] = "#"

            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                nr = row + dr
                nc = col + dc

                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and board[nr][nc] != "#"
                ):
                    dfs(nr, nc, node)

            board[row][col] = char

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

        return result

solution = Solution()

# Provided example 1
board = [
    ["o","a","a","n"],
    ["e","t","a","e"],
    ["i","h","k","r"],
    ["i","f","l","v"]
]
words = ["oath","pea","eat","rain"]
assert sorted(solution.findWords(board, words)) == ["eat", "oath"]  # standard example

# Provided example 2
board = [["a","b"],["c","d"]]
words = ["abcb"]
assert solution.findWords(board, words) == []  # cannot reuse cells

# Single cell success
board = [["a"]]
words = ["a"]
assert solution.findWords(board, words) == ["a"]  # smallest valid board

# Single cell failure
board = [["a"]]
words = ["b"]
assert solution.findWords(board, words) == []  # missing character

# Shared prefixes
board = [
    ["a","r","t"],
    ["i","s","t"],
    ["t","o","p"]
]
words = ["art", "artist", "arts"]
result = sorted(solution.findWords(board, words))
assert result == ["art"]  # only one valid prefix-based word

# Duplicate traversal prevention
board = [
    ["a","a"],
    ["a","a"]
]
words = ["aaaa"]
assert solution.findWords(board, words) == ["aaaa"]  # valid without reuse

# Multiple valid words
board = [
    ["c","a","t"],
    ["r","r","e"],
    ["t","o","n"]
]
words = ["cat", "car", "tone", "ton"]
result = sorted(solution.findWords(board, words))
assert result == ["cat", "ton", "tone"]  # multiple discoveries

# Empty result
board = [
    ["x","y"],
    ["z","w"]
]
words = ["abc", "def"]
assert solution.findWords(board, words) == []  # no matching prefixes
Test Why
Standard example Verifies core functionality
Cannot reuse cells Ensures visited handling is correct
Single cell success Smallest successful input
Single cell failure Smallest failing input
Shared prefixes Validates Trie efficiency and correctness
Repeated letters Ensures backtracking works correctly
Multiple valid words Confirms multiple discoveries are returned
Empty result Ensures invalid searches terminate properly

Edge Cases

One important edge case occurs when multiple words share prefixes. For example, words like "art", "artist", and "arts" partially overlap in the Trie. A naive implementation may redundantly search the same board regions multiple times. The Trie-based solution handles this naturally because shared prefixes reuse the same Trie path.

Another critical edge case involves repeated characters on the board. Consider a board filled with "a" characters and a word like "aaaa". Without proper visited tracking, DFS may incorrectly reuse the same cell multiple times. The implementation prevents this by temporarily marking cells with "#" during exploration.

A third important edge case is when no valid prefixes exist from a starting position. Without Trie pruning, DFS would still explore many unnecessary paths. In this solution, DFS immediately terminates if the current board character does not exist in the Trie node, dramatically reducing wasted work.

A final subtle edge case occurs when the same word can be discovered through multiple paths. Since the problem requires unique output words, duplicate additions must be prevented. The implementation handles this by clearing node.word after the first successful discovery.