LeetCode · #79

Word Search Solution

Given an m × n grid of characters and a string word, return true if the word exists in the grid via adjacent (horizontally/vertically) cells, each cell used at most once.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #79

🏗️

Pattern

Backtracking — grid DFS

Given an m × 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 — horizontally or vertically. The same cell may not be used more than once per path.

Example

 Input: board = [["A","B","C","E"],
                 ["S","F","C","S"],
                 ["A","D","E","E"]]
         word = "ABCCED" Output: true // Path: (0,0)A → (0,1)B → (0,2)C → (1,2)C → (2,2)E → (2,1)D 

Constraints

 • m == board.length, n == board[i].length • 1 ≤ m, n ≤ 6  ← small grid, exhaustive backtracking is feasible • 1 ≤ word.length ≤ 15 • board and word consist of only uppercase and lowercase English letters 

Section Two · Approach 1

Brute DFS with Visited Set — O(m·n·4ᴸ)

From every cell, launch a DFS. Maintain a separate HashSet of visited coordinates. If the current cell matches the current character of the word, recurse into all 4 neighbors; otherwise backtrack. Clear the set before each new starting cell.

Why it works

Since we track visited cells in a set, no cell is revisited in a single path. Trying all starting positions and exploring all valid 4-directional paths guarantees correctness.

Why we can do better

Problem: A HashSet of coordinate pairs allocates objects on every recursive call. The optimal approach marks visited cells in-place by overwriting the cell with a sentinel character (e.g., '#'), then restoring it on backtrack. This eliminates all allocations for the visited state and is O(1) per cell check.

Java — DFS with visited Set

 import java.util.*;
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (dfs(board, r, c, word, 0, new HashSet<>())) return true;
return false;
    }
private boolean dfs(char[][] b, int r, int c, String w,
int k, Set<Integer> vis) {
if (k == w.length()) return true;
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length) return false;
int key = r * b[0].length + c;
if (vis.contains(key) || b[r][c] != w.charAt(k)) return false;
        vis.add(key);
boolean found = dfs(b,r+1,c,w,k+1,vis)||dfs(b,r-1,c,w,k+1,vis)||
dfs(b,r,c+1,w,k+1,vis)||dfs(b,r,c-1,w,k+1,vis);
        vis.remove(key);
return found;
    }
}

Python — DFS with visited Set

 class Solution:
def exist(self, board: list[list[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        vis = set()
def dfs(r: int, c: int, k: int) -> bool:
if k == len(word): return True if r < 0 or r >= m or c < 0 or c >= n: return False if (r, c) in vis or board[r][c] != word[k]: return False
vis.add((r, c))
            found = (dfs(r+1,c,k+1) or dfs(r-1,c,k+1) or dfs(r,c+1,k+1) or dfs(r,c-1,k+1))
            vis.discard((r, c))
return found
return any(dfs(r, c, 0) for r in range(m) for c in range(n))

Metric	Value
Time	O(m · n · 4ᴸ) where L = word length
Space	O(L) call stack + O(L) visited set per path

Section Three · Approach 2

In-place Backtracking — O(m·n·4ᴸ)

Replace the visited set by marking the current cell with a sentinel character '#' before recursing and restoring it afterward. This achieves the same "no revisit" invariant with zero extra memory per call.

💡 Mental model: Think of walking through a corn maze and leaving a thumbtack in each square you step on. If you reach a dead end, you pull out your thumbtack and back up. The tack IS the visited marker — you don't need a separate list of "cells I've been to." When you leave a cell (backtrack), you remove the tack so future explorers can use that cell again from a different path.

Algorithm — in-place sentinel backtracking

Search all starting positions: try every cell (r, c) as the start when it matches word[0].
DFS(r, c, k): check bounds, then check board[r][c] == word[k].
Mark visited: set board[r][c] = '#' — sentinel that matches nothing.
Recurse: explore all 4 neighbors for character word[k+1].
Restore: set board[r][c] back to original character (backtrack).
Return true as soon as any path succeeds (short-circuit).

🎯 When to recognize this pattern:

Any "path exists in 2D grid" problem where cells cannot be reused in a single path.
The 4-direction DFS + in-place marking is a direct template.
It also appears in LC 212 (Word Search II — add a Trie), LC 200 (Number of Islands — flood fill), and LC 130 (Surrounded Regions).
The signal: "find a path on a grid, no revisit."

Early termination — frequency pruning:

Before starting DFS, count character frequencies in the board and compare to the word.
If any character in the word appears more times in the word than in the board, immediately return false.
This can eliminate the entire DFS for impossible words in O(m·n + L) time.

Section Four · Trace

Visual Walkthrough

Trace searching for "ABCCED" in the example grid. The successful path is shown step-by-step.

Word Search — Backtracking Path Trace (word = "ABCCED")

Section Five · Implementation

Code — Java & Python

Java — In-place sentinel backtracking

 class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (dfs(board, r, c, word, 0)) return true;
return false;
    }
private boolean dfs(char[][] b, int r, int c,
String word, int k) {
if (k == word.length()) return true; // all chars matched if (r < 0 || r >= b.length ||
            c < 0 || c >= b[0].length) return false;
if (b[r][c] != word.charAt(k)) return false;
char tmp = b[r][c];
        b[r][c] = '#'; // sentinel — prevent revisit boolean found = dfs(b,r+1,c,word,k+1) || dfs(b,r-1,c,word,k+1) ||
dfs(b,r,c+1,word,k+1) || dfs(b,r,c-1,word,k+1);

        b[r][c] = tmp; // restore — backtrack return found;
    }
}

Python — In-place sentinel backtracking

 class Solution:
def exist(self, board: list[list[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
def dfs(r: int, c: int, k: int) -> bool:
if k == len(word): return True # full match if r < 0 or r >= m or c < 0 or c >= n: return False if board[r][c] != word[k]: return False
tmp, board[r][c] = board[r][c], '#' # mark visited
found = (dfs(r+1,c,k+1) or dfs(r-1,c,k+1) or dfs(r,c+1,k+1) or dfs(r,c-1,k+1))
            board[r][c] = tmp # restore — backtrack return found
return any(dfs(r, c, 0) for r in range(m) for c in range(n))

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute DFS + HashSet	O(m·n·4ᴸ)	O(L) set + O(L) stack	Extra set allocation per call; harder to optimize
DFS + boolean[][ ] visited	O(m·n·4ᴸ)	O(m·n + L)	Separate grid copy — extra O(m·n) space
In-place sentinel ← optimal	O(m·n·4ᴸ)	O(L) call stack only	Mutates input temporarily; zero extra space for visited

Why 4ᴸ and not 4^(m·n)?:

At each of the L characters in the word, we explore at most 4 directions.
Practically, one direction is always the cell we came from (which is marked '#'), so the branching factor is ≤ 3.
But in the worst case (no path is pruned until character L), it is still O(4ᴸ) per starting cell, giving O(m·n·4ᴸ) total.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Word longer than all cells	1×1 grid, 5-char word	Only 1 cell exists; function returns false after matching at most 1 char.
Single cell equals word	`[["A"]], word="A"`	`k=0` matches, recursion with `k=1` returns true immediately.
Word includes same char twice	`word="AA"` on grid `[["A","A"]]`	Sentinel '#' prevents revisiting the same cell as A for the second A.
Word not present	any grid, word not in grid	All DFS branches exhaust without returning true → return false.
Negative or boundary start	word starts at corner	Neighbors go out of bounds → bounds check returns false, no crash.
Forgetting to restore cell	any	Leaving '#' in the board means later starting positions see a corrupted grid — false negatives.

⚠ Common Mistake: Not restoring board[r][c] after a failed DFS branch. If you mark a cell '#' and only restore it on success, any subsequent starting position that passes through that cell will erroneously treat it as already visited. The restore must happen unconditionally after the recursive call — whether the call returned true or false.

← Back to Backtracking problems

LearningTree

LC 79 · Word Search — Solution & Explanation | DSA Guide