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

Word Search

An interactive visualization of DFS backtracking on a character grid. Watch the algorithm explore paths letter by letter, backtracking when a path doesn't match the target word.

DFS LeetCode 79 ↗ Medium

The Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can 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.

Interactive Visualization

Grid (rows separated by commas)

Word

Preset

Speed:

Character Grid

Code

fun exist(board: Array<CharArray>, word: String): Boolean {    val rows = board.size; val cols = board[0].size    fun dfs(r: Int, c: Int, i: Int): Boolean {        if (i == word.length) {            return true        }        if (r < 0 || r >= rows ||            c < 0 || c >= cols ||            board[r][c] != word[i]) {            return false        }        val temp = board[r][c]        board[r][c] = '#'  // mark visited        val found = (dfs(r + 1, c, i + 1) ||                     dfs(r - 1, c, i + 1) ||                     dfs(r, c + 1, i + 1) ||                     dfs(r, c - 1, i + 1))        board[r][c] = temp  // backtrack        return found    }    for (r in 0 until rows) {        for (c in 0 until cols) {            if (dfs(r, c, 0)) {                return true            }        }    }    return false}

def exist(board, word):    rows, cols = len(board), len(board[0])    def dfs(r, c, i):        if i == len(word):            return True        if (r < 0 or r >= rows or            c < 0 or c >= cols or            board[r][c] != word[i]):            return False        temp = board[r][c]        board[r][c] = '#'  # mark visited        found = (dfs(r+1, c, i+1) or                 dfs(r-1, c, i+1) or                 dfs(r, c+1, i+1) or                 dfs(r, c-1, i+1))        board[r][c] = temp  # backtrack        return found    for r in range(rows):        for c in range(cols):            if dfs(r, c, 0):                return True    return False

Current Step

Press Step or Play to begin.

How It Works

Key Insight

DFS with backtracking — temporarily mark cells as visited to prevent reuse, explore all 4 directions (down, up, right, left), then unmark (backtrack) so the cell is available for other paths. Try every cell as a potential starting point until the word is found or all possibilities are exhausted.

The Algorithm

Iterate over every cell (r, c) in the grid as a potential starting position.
DFS from (r, c) trying to match word[i]:
— Base case: if i == len(word), all characters matched — return True.
— Bounds/mismatch check: if out of bounds or board[r][c] != word[i], return False.
— Mark visited: temporarily replace board[r][c] with '#'.
— Explore: recursively try all 4 neighbors for word[i+1].
— Backtrack: restore board[r][c] to its original character.
If any starting cell's DFS returns True, the word exists. Otherwise return False.

Complexity

Time O(m * n * 4^L)

Space O(L)

Where m * n is the grid size and L is the word length. For each of the m * n starting cells, the DFS can branch into 4 directions at each of the L levels — worst case 4^L paths. Space is O(L) for the recursion stack depth (the word length).