LeetCode 79: Word Search

An Interactive Visual Explainer

Idea By: Chetan Pachpande | Executed By: Gemini

Back to Home

Problem Description

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.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

Complexity Analysis

Time Complexity: O(N * M * 4^L)
Where N x M are board dimensions and L is the word length. We may start a search from any of the N*M cells, and each search can branch up to 4 directions for L steps.

Space Complexity: O(L)
The space is dominated by the recursion stack, which can go as deep as the length of the word.

Intuition

This problem is a classic search scenario perfectly suited for a **Depth First Search (DFS)** with **backtracking**.

Iterate and Initiate: We must try starting a search from every single cell, as the word can begin anywhere.
Depth First Search (DFS): From a valid starting cell, we recursively explore neighbors (up, down, left, right) to find the next character of the word.
Marking (Avoid Reuse): To prevent using the same cell twice in a path, we mark it as visited (e.g., with '#') before exploring from it.
Backtracking: If a path fails, we must "un-mark" the cell, restoring its original character. This allows it to be used in different future paths.

Step-by-Step Code

Live Visualization

Board (JSON format)

Word

Algorithm States

Status: Idle Current Cell: N/A Word Index (i): N/A Temp Char: N/A Result (res): N/A

Call Stack

Stack is empty

Execution Commands

Log of Step Execution

Press "Run Visualization" to begin.

Algorithm Flowchart

graph TD A[Start] --> B(Loop for each cell); B --> C{Call dfs}; C -- returns true --> D[Return True]; C -- returns false --> B; B -- all cells checked --> E[Return False]; subgraph DFS F[dfs start] --> G{"i == word.length"}; G -- Yes --> H[Return True]; G -- No --> I{"Cell valid?"}; I -- No --> J[Return False]; I -- Yes --> K[Mark cell]; K --> L[Recurse on neighbors]; L --> M[Backtrack]; M --> N[Return result]; end

Commented Java Code


public class Solution {
    private int ROWS, COLS;

    /**
     * Main function to check if the word exists on the board.
     */
    public boolean exist(char[][] board, String word) {
        ROWS = board.length;
        COLS = board[0].length;

        // Iterate through every cell on the board to start the search.
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                // Start DFS from cell (r, c) for the first character of the word.
                if (dfs(board, word, r, c, 0)) {
                    return true; // Word found!
                }
            }
        }
        return false; // Word not found after checking all possibilities.
    }

    /**
     * Recursive Depth-First Search with backtracking.
     */
    private boolean dfs(char[][] board, String word, int r, int c, int i) {
        // Base Case 1: Success! We've found all characters of the word.
        if (i == word.length()) {
            return true;
        }
        
        // Base Case 2: Failure conditions for the current path.
        if (r < 0 || c < 0 || r >= ROWS || c >= COLS || // Out of bounds
            board[r][c] != word.charAt(i) ||           // Character doesn't match
            board[r][c] == '#') {                      // Cell already visited in this path
            return false;
        }

        // --- Action ---
        // Mark the cell as visited for the current path.
        char temp = board[r][c];
        board[r][c] = '#';

        // --- Recurse ---
        // Explore all 4 neighbors.
        boolean res = dfs(board, word, r + 1, c, i + 1) || // Down
                      dfs(board, word, r - 1, c, i + 1) || // Up
                      dfs(board, word, r, c + 1, i + 1) || // Right
                      dfs(board, word, r, c - 1, i + 1);   // Left

        // --- Backtrack ---
        // Un-mark the cell, so it can be used in other paths.
        board[r][c] = temp;

        return res;
    }