Word Search

Given an M×N board of characters and a word, determine if the word exists by sequentially matching adjacent cells (horizontal or vertical). The classic solution uses DFS backtracking from every matching start cell, with a visited grid to prevent reusing the same cell. This lesson covers LeetCode 79 and implementations in C, Java, and Python with trace tables.

Overview

Word Search is grid DFS with a string index instead of a path string. Each step checks whether the current cell matches the next character; if the full word matches, return true. Failed branches backtrack by unmarking visited cells.

Board (LeetCode 79 classic)          word = "ABCCED"

  A B C E                            (0,0)A → (0,1)B → (0,2)C
  S F C S         match path →       → (1,2)C → (2,2)E → (2,3)D  ✓
  A D E E

Adjacent moves only (no diagonals); each cell used once per path

Problem Statement

Input: 2D character board board[m][n] and string word.

Output: true if word can be constructed from sequentially adjacent cells; otherwise false.

Rules:

• Letters must match in order along the word.
• Only horizontal or vertical neighbors count (4-directional).
• The same cell cannot appear twice in one search path.

Examples (classic board):

• "ABCCED" → true
• "SEE" → true (starts at (1,3) S)
• "ABCB" → false (would need to reuse B at (0,1))

Backtracking Algorithm

1. For each cell (row, col) where board[row][col] == word[0], run DFS.
2. DFS(row, col, index):
   • If index == len(word), return true.
   • If out of bounds, visited, or char mismatch → return false.
   • Mark visited[row][col] = true.
   • Try four neighbors with index + 1; if any returns true, propagate.
   • Unmark visited and return false.

Character Pruning

Before recursing, reject immediately when:

• board[row][col] != word[index] — character mismatch
• Cell already visited on current path
• row or col out of bounds

In-place trick: Temporarily replace board[row][col] with '#' instead of a separate visited matrix — restore on backtrack (saves O(m×n) space).

Code (C, Java, Python)

Python

def exist(board, word):
    """Word Search — DFS backtracking with visited grid."""
    if not board or not board[0]:
        return False
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]
    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]

    def dfs(row, col, index):
        if index == len(word):
            return True
        if (row < 0 or row >= rows or col < 0 or col >= cols
                or visited[row][col] or board[row][col] != word[index]):
            return False
        visited[row][col] = True
        for k in range(4):
            if dfs(row + dr[k], col + dc[k], index + 1):
                return True
        visited[row][col] = False
        return False

    for r in range(rows):
        for c in range(cols):
            if board[r][c] == word[0] and dfs(r, c, 0):
                return True
    return False


if __name__ == "__main__":
    grid = [
        list("ABCE"),
        list("SFCS"),
        list("ADEE"),
    ]
    print(exist(grid, "ABCCED"))  # True
    print(exist(grid, "ABCB"))    # False

Java

public class WordSearch {

    private static final int[] DR = {1, -1, 0, 0};
    private static final int[] DC = {0, 0, 1, -1};

    private static boolean dfs(char[][] board, boolean[][] visited,
                               String word, int row, int col, int index) {
        if (index == word.length()) return true;
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length)
            return false;
        if (visited[row][col] || board[row][col] != word.charAt(index))
            return false;

        visited[row][col] = true;
        for (int k = 0; k < 4; k++) {
            if (dfs(board, visited, word, row + DR[k], col + DC[k], index + 1))
                return true;
        }
        visited[row][col] = false;
        return false;
    }

    public static boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (board[r][c] == word.charAt(0) && dfs(board, visited, word, r, c, 0))
                    return true;
        return false;
    }
}

C

#include <stdbool.h>
#include <string.h>

int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};

bool dfs(char board[][10], bool visited[][10], const char *word,
         int rows, int cols, int row, int col, int index) {
    int k, nr, nc;
    if (word[index] == '\0') return true;
    if (row < 0 || row >= rows || col < 0 || col >= cols) return false;
    if (visited[row][col] || board[row][col] != word[index]) return false;

    visited[row][col] = true;
    for (k = 0; k < 4; k++) {
        nr = row + dr[k];
        nc = col + dc[k];
        if (dfs(board, visited, word, rows, cols, nr, nc, index + 1))
            return true;
    }
    visited[row][col] = false;
    return false;
}

Output & Trace

Sample results (LeetCode board)

Partial trace — matching "ABCCED"

LeetCode 79 & 212

Optimizations

• In-place visited: Mark cells with '#' — O(1) extra space beyond recursion.
• Early return: Stop at first successful DFS — no need to search all starts after match.
• Trie (LC 212): Share prefix exploration across many dictionary words.
• Frequency prune: If board lacks enough of a rare letter, return false before DFS.

Approach Comparison

L = word length, m×n = board size.

Real-Life Applications

Interview Tips

1. Clarify: 4-directional only, no cell reuse on one path.
2. Loop all cells for first-char match, then DFS with index.
3. Always unmark visited (or restore char) on backtrack.
4. Mention in-place '#' trick if asked to optimize space.
5. Complexity: O(m×n×4^L) worst case; L = word length.
6. Connect to rat in a maze and pruning techniques.