This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#212) before relying on it.

Word Search II

An interactive visualization of the Trie + DFS approach to Word Search II. Watch how a prefix tree prunes invalid paths while DFS explores the board to find all dictionary words.

Trie LeetCode 212 ↗ Hard

The Problem

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Interactive Visualization

Board (rows separated by ;)

Words (comma-separated)

Preset

Speed:

Board

Found Words

None yet

Trie Structure

Code

fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {    val root = HashMap<Char, Any>()    for (word in words) {        var node = root        for (c in word) {            node = node.getOrPut(c) { HashMap<Char, Any>() } as HashMap        }        node['#'] = word  // end marker    }    val m = board.size; val n = board[0].size    val result = mutableListOf<String>()    fun dfs(i: Int, j: Int, node: HashMap<Char, Any>) {        val char = board[i][j]        if (char !in node) return        val nextNode = node[char] as HashMap<Char, Any>        if ('#' in nextNode) {            result.add(nextNode['#'] as String)            nextNode.remove('#')  // avoid dups        }        board[i][j] = '.'  // mark visited        for ((di, dj) in listOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)) {            val ni = i + di; val nj = j + dj            if (ni in 0 until m && nj in 0 until n) {                if (board[ni][nj] != '.') {                    dfs(ni, nj, nextNode)                }            }        }        board[i][j] = char  // restore    }    for (i in 0 until m) {        for (j in 0 until n) {            dfs(i, j, root)        }    }    return result}

def findWords(board, words):    root = {}    for word in words:        node = root        for c in word:            node = node.setdefault(c, {})        node['#'] = word  # end marker    m, n = len(board), len(board[0])    result = []    def dfs(i, j, node):        char = board[i][j]        if char not in node:            return        next_node = node[char]        if '#' in next_node:            result.append(next_node['#'])            del next_node['#']  # avoid dups        board[i][j] = '.'  # mark visited        for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:            ni, nj = i + di, j + dj            if 0 <= ni < m and 0 <= nj < n:                if board[ni][nj] != '.':                    dfs(ni, nj, next_node)        board[i][j] = char  # restore    for i in range(m):        for j in range(n):            dfs(i, j, root)    return result

Current Step

Press Step or Play to begin.

How It Works

Key Insight

Searching for each word independently with DFS would be O(words * m * n * 4^L). Instead, we build a Trie (prefix tree) from all words and run a single DFS from each cell. The trie lets us check all words simultaneously: if the current path does not match any prefix in the trie, we prune that branch immediately, avoiding exponential work.

The Algorithm

Build the Trie: Insert all words. Each node is a dictionary of children. Mark end-of-word nodes with the complete word string.
DFS from every cell: For each cell (i, j), start a DFS with the trie root.
At each DFS step: Check if board[i][j] is a child of the current trie node. If not, return (prune). If yes, move to that child node.
Word found: If the current trie node has an end marker '#', add the word to results and delete the marker to avoid duplicates.
Mark visited: Temporarily replace board[i][j] with '.' to prevent revisiting, then recurse into all four neighbors. Restore the cell afterward (backtrack).

Why Trie + DFS?

The trie enables prefix pruning: if no word in the dictionary starts with the characters along the current path, we stop immediately. This is far more efficient than running a separate DFS for each word. Additionally, deleting end markers after finding a word prevents duplicate results without needing an extra set.

Complexity

Time O(m * n * 4^L)

Space O(W * L)

Where m * n is the board size, L is the maximum word length, and W is the total number of words. In practice, trie pruning makes this much faster. The trie stores at most W * L nodes.