14.10 Word Search

14.10.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 79
• Difficulty: Medium
• URL: https://leetcode.com/problems/lc-word-search/
• Tags: Grind 75, Blind 75, NeetCode 150
• Techniques: Backtracking: Mark-Unmark, Depth First Search, Matrix, Backtracking

14.10.2 Description

Given a board of characters and a target word, check if the word can be constructed from sequentially adjacent cells (horizontal or vertical). Each cell can be used at most once.

14.10.3 Examples

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

14.10.4 Constraints

• 1 <= board.length, board[0].length <= 6
• 1 <= word.length <= 15

14.10.5 Solution - DFS Backtracking

14.10.5.1 Walkthrough

Try every cell as a starting point by iterating through the entire board. For each starting position, create a fresh visited array to track which cells are used in the current path. Use DFS to recursively match characters by exploring all four directions (up, down, left, right).

Key Backtracking Steps: 1. Mark: Mark the current cell as visited before exploring neighbors 2. Explore: Recursively try all four directions with the next character 3. Unmark: Restore the cell to unvisited before returning (critical for backtracking!)

This mark-unmark pattern ensures cells can be reused when trying different starting positions or different paths. If we successfully match all characters (reach the end of the word), return true. Otherwise, backtrack and try other paths.

14.10.5.2 Analysis

• Time Complexity: O(m × n × 4^L) where L is the word length. For each of m × n starting positions, DFS explores up to 4^L paths (4 directions at each of L steps, though pruned by visited checks)
• Space Complexity: O(m × n + L) where O(m × n) is for the visited array and O(L) is the recursion stack depth

14.10.5.3 Implementation Steps

1. Loop over all cells (i, j) in the board as potential starting positions
2. For each starting position, create a fresh visited[m][n] boolean array
3. Call dfs(board, visited, i, j, word, 0) to attempt matching from that position
4. DFS Base Cases:
   • If index >= word.length(), return true (found complete word)
   • If out of bounds, return false
   • If already visited OR character doesn’t match, return false
5. DFS Recursive Case:
   • Mark visited[i][j] = true
   • Recursively explore all 4 directions with index + 1
   • Backtrack: Set visited[i][j] = false before returning
6. Return true if any starting position succeeds

14.10.5.4 Code - Java

public boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            boolean[][] visited = new boolean[board.length][board[0].length];

            boolean result = dfs(board, visited, i, j, word, 0);

            if (result) {
                return true;
            }
        }
    }

    return false;
}

private boolean dfs(char[][] board, boolean[][] visited, int i, int j, String word, int index) {
    // End of word reached - success
    if (index >= word.length()) {
        return true;
    }

    // Out of bounds check
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
        return false;
    }

    // Already visited OR character doesn't match
    if (visited[i][j] || word.charAt(index) != board[i][j]) {
        return false;
    }

    // Mark current cell as visited
    visited[i][j] = true;

    // Explore all four directions
    boolean found =
        dfs(board, visited, i + 1, j, word, index + 1) || // down
        dfs(board, visited, i - 1, j, word, index + 1) || // up
        dfs(board, visited, i, j + 1, word, index + 1) || // right
        dfs(board, visited, i, j - 1, word, index + 1);   // left

    // BACKTRACK: Unmark visited cell before returning
    visited[i][j] = false;

    return found;
}