Stage 2: Recursive Thinking·Backtracking

Medium#796 min readBacktrackingGridDFSLeetCode

Word Search

Grid DFS with visited mark encoded in the board

2D grid backtracking. Mark visited, explore 4 directions, unmark.

Published Apr 16, 2026

Problem

Given an m × n grid of characters and a string word, return true if the word can be found in the grid by starting at any cell and stepping horizontally or vertically to adjacent cells. A cell may not be reused within one path.

Input

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

Output

true

Input

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Output

true

Input

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

Output

false

Explanation

The B at (0,1) cannot be reused.

Intuition

From any starting cell, run a DFS that tries each of the four neighbors, matching the word character by character. Two wrinkles:

Don't revisit. A separate visited grid works, but the idiomatic trick is to temporarily mutate the board — write a sentinel (#) into the cell during the recursive call and restore it on the way out. Zero extra memory, clean back-tracking.
Start anywhere. Try every cell as a starting point until one succeeds.

The branching factor is 4 (neighbors), the depth is L = word.length. Worst case m · n · 4^L, but in practice most branches die at the first mismatch.

Approach

DFS with in-place marking

TimeO(m·n·4^L)

SpaceO(L)

Recommended

Try each cell as a start. From there, recurse into all four neighbors with the next character. Mutate the current cell to a sentinel before recursing and restore after.

impl Solution {
    pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
        let rows = board.len();
        let cols = board[0].len();
        let word: Vec<char> = word.chars().collect();
        let mut board = board;
        fn dfs(
            r: isize,
            c: isize,
            k: usize,
            word: &[char],
            board: &mut Vec<Vec<char>>,
            rows: usize,
            cols: usize,
        ) -> bool {
            if k == word.len() {
                return true;
            }
            if r < 0
                || c < 0
                || r >= rows as isize
                || c >= cols as isize
                || board[r as usize][c as usize] != word[k]
            {
                return false;
            }
            let saved = board[r as usize][c as usize];
            board[r as usize][c as usize] = '#';
            let found = dfs(r + 1, c, k + 1, word, board, rows, cols)
                || dfs(r - 1, c, k + 1, word, board, rows, cols)
                || dfs(r, c + 1, k + 1, word, board, rows, cols)
                || dfs(r, c - 1, k + 1, word, board, rows, cols);
            board[r as usize][c as usize] = saved;
            found
        }
        for r in 0..rows {
            for c in 0..cols {
                if dfs(r as isize, c as isize, 0, &word, &mut board, rows, cols) {
                    return true;
                }
            }
        }
        false
    }
}

Rust · runnable

function exist(board: string[][], word: string): boolean {
  const rows = board.length;
  const cols = board[0].length;
  const dfs = (r: number, c: number, k: number): boolean => {
    if (k === word.length) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
    if (board[r][c] !== word[k]) return false;
    const saved = board[r][c];
    board[r][c] = '#';
    const found =
      dfs(r + 1, c, k + 1) ||
      dfs(r - 1, c, k + 1) ||
      dfs(r, c + 1, k + 1) ||
      dfs(r, c - 1, k + 1);
    board[r][c] = saved;
    return found;
  };
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

TypeScript · runnable

DFS with separate visited grid

TimeO(m·n·4^L)

SpaceO(m·n)

Same algorithm, but use a boolean grid rather than mutating the board. Pros: non-destructive, thread-safe if the board is shared; cons: extra O(m · n) memory.

Prefer this variant when the input is not yours to mutate (e.g. a library boundary).

impl Solution {
    pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
        let rows = board.len();
        let cols = board[0].len();
        let word: Vec<char> = word.chars().collect();
        let mut seen = vec![vec![false; cols]; rows];
        fn dfs(
            r: isize,
            c: isize,
            k: usize,
            word: &[char],
            board: &[Vec<char>],
            seen: &mut Vec<Vec<bool>>,
        ) -> bool {
            if k == word.len() {
                return true;
            }
            if r < 0 || c < 0 || r >= board.len() as isize || c >= board[0].len() as isize {
                return false;
            }
            let (rr, cc) = (r as usize, c as usize);
            if seen[rr][cc] || board[rr][cc] != word[k] {
                return false;
            }
            seen[rr][cc] = true;
            let found = dfs(r + 1, c, k + 1, word, board, seen)
                || dfs(r - 1, c, k + 1, word, board, seen)
                || dfs(r, c + 1, k + 1, word, board, seen)
                || dfs(r, c - 1, k + 1, word, board, seen);
            seen[rr][cc] = false;
            found
        }
        for r in 0..rows {
            for c in 0..cols {
                if dfs(r as isize, c as isize, 0, &word, &board, &mut seen) {
                    return true;
                }
            }
        }
        false
    }
}

Rust · runnable

function exist(board: string[][], word: string): boolean {
  const rows = board.length;
  const cols = board[0].length;
  const seen: boolean[][] = Array.from({ length: rows }, () =>
    new Array(cols).fill(false)
  );
  const dfs = (r: number, c: number, k: number): boolean => {
    if (k === word.length) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
    if (seen[r][c] || board[r][c] !== word[k]) return false;
    seen[r][c] = true;
    const found =
      dfs(r + 1, c, k + 1) ||
      dfs(r - 1, c, k + 1) ||
      dfs(r, c + 1, k + 1) ||
      dfs(r, c - 1, k + 1);
    seen[r][c] = false;
    return found;
  };
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

TypeScript · runnable

Trace

Searching for "SEE" in the example board:

A B C E
S F C S
A D E E

Start from (1, 0) = 'S':

step	cell	matched so far	action
1	(1,0) 'S'	S	recurse neighbors
2	(2,0) 'A'	-	mismatch
3	(0,0) 'A'	-	mismatch
4	(1,1) 'F'	-	mismatch
5	-	-	need second S — try (1,3)
6	(1,3) 'S'	S	recurse
7	(0,3) 'E'	SE	recurse
8	(1,3)	-	already # (marked)
9	-	-	try (0,2) 'C' mismatch; up/right OOB
10	(2,3) 'E'	SEE	k==3 return true

The in-place mark keeps us from walking back over visited cells. Restoration on unwind means the next start attempt sees the clean board.

Edge cases

Single character word — every cell with that value returns true.
Word longer than board cells — can't fit without reuse; returns false.
Sentinel character appears in input — rare, but # must not be a possible board value. With uppercase letters as input, we're safe.
Grid with 1 row or 1 column — same algorithm; boundary checks prevent out-of-bounds.

Takeaway

In-place marking with restoration is the grid equivalent of the used[] array. The idea generalizes: any backtracking over a mutable container can temporarily overwrite state and restore it on the way out. It cuts memory and often runs faster than a parallel visited structure because of cache locality.

Medium#200

Number of Islands

Flood fill with DFS. The grid IS the graph — each cell is a node.

Medium#131

Palindrome Partitioning

Backtrack on where to cut. Precompute palindrome checks with DP.

Hard#51

N-Queens

Row-by-row placement with column/diagonal constraint checking. Classic.