Difficulty: MediumBacktracking

Word Search

Problem in Plain English

Given a grid of letters and a word, decide whether the word can be traced through cells that touch horizontally or vertically without reusing any cell.

Problem Statement

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word is built from letters of sequentially adjacent cells that share a horizontal or vertical side, and no cell may be used twice within one traced word.

Constraints

m == board.length
n == board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word hold only English letters, upper and lower case.

Examples

Example 1

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

Trace A at (0,0) right to B and C, down to C, then down to E and left to D.

Example 2

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

Trace S at (1,3) down to E at (2,3) and left to E at (2,2).

Example 3

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

The second B would need a cell that is already used in the current path.

Example 4

Input: board = [["a"]], word = "A"
Output: false

Matching is case-sensitive. The one lowercase cell does not supply the uppercase A; there is no adjacent alternative.

Intuition

A matching letter is only a possible next step: its neighbors must also supply the remaining letters without reusing a cell. For Example 1, the path A, B, C, C, E, D follows six distinct cells. Keep a record of the cells in the current path, try neighbors in turn, then undo that record on return. Undoing matters even after success because the caller should receive the same board it supplied. Cells used in one failed path may be used in another.

Approaches

DFS With Visited Set

Solution Details

Reveal DFS With Visited Set: intuition, complexity, and code

Intuition

Every cell matching the first letter can start the word, and the rest of the word is a path problem through four neighbours from there. A depth-first search carrying a visited record enforces the no-reuse rule and reports success the moment the last letter matches.

Step-by-Step Logic

If the word length exceeds the cell count, return false. Otherwise scan every cell as a possible start and call dfs(r,c,0). For Example 1 the first start is (0,0), holding A.
In DFS first accept i equal to the word length: the previous call consumed the last letter. Otherwise reject out-of-bounds cells, reused cells, and mismatched letters. Record a matching cell as used for the duration of its descendants.
Try neighbors in the code order: down, up, right, left, passing i + 1. Example 1 first rejects S and an out-of-bounds cell while seeking B, then reaches B at (0,1).
Continue through (0,2)=C, (1,2)=C, (2,2)=E and (2,1)=D. The table lists failed probes as well as successful moves. When the extra call has i = 6, the base case succeeds without consuming another cell.
Store the combined Boolean result, undo the current cell mark, then return that result. This cleanup runs even on a successful branch. After all six frames unwind, return true with the board fully restored; if every start fails, return false.

Why It Works

On entry to dfs(r,c,i), the marked cells are exactly the distinct cells supplying word[0:i]. A call can extend the path only when the cell is in bounds, unused, and matches word[i]. Trying all four side neighbors covers every possible next step and excludes diagonal moves. The visited record prevents reuse; removing a cell after all child calls restores the parent path. Once i equals the word length, all letters have already been supplied, so success is valid even before checking the proposed next coordinates. Every legal path starts at one of the scanned cells and follows one of these branches, proving completeness. Short-circuiting stops after a success, but cleanup still executes in every active frame. The length guard is safe because a path cannot contain more cells than the board.

Dry Run

DFS With Visited Set: variable states at each step
cell / i	expected / observed	active path on entry	action / restore
(0,0) / 0	A / A	empty	add cell to visited; descend
(1,0) / 1	B / S	0,0	false: mismatch
(-1,0) / 1	B / outside	0,0	false: bounds
(0,1) / 1	B / B	0,0	add cell to visited; descend
(1,1) / 2	C / F	0,0; 0,1	false: mismatch
(-1,1) / 2	C / outside	0,0; 0,1	false: bounds
(0,2) / 2	C / C	0,0; 0,1	add cell to visited; descend
(1,2) / 3	C / C	0,0; 0,1; 0,2	add cell to visited; descend
(2,2) / 4	E / E	0,0; 0,1; 0,2; 1,2	add cell to visited; descend
(3,2) / 5	D / outside	0,0; 0,1; 0,2; 1,2; 2,2	false: bounds
(1,2) / 5	D / C	0,0; 0,1; 0,2; 1,2; 2,2	false: already used
(2,3) / 5	D / E	0,0; 0,1; 0,2; 1,2; 2,2	false: mismatch
(2,1) / 5	D / D	0,0; 0,1; 0,2; 1,2; 2,2	add cell to visited; descend
(3,1) / 6	word consumed	0,0; 0,1; 0,2; 1,2; 2,2; 2,1	true before bounds; consumes no new cell
(2,1) / 5	matched D	0,0; 0,1; 0,2; 1,2; 2,2	remove cell; return true
(2,2) / 4	matched E	0,0; 0,1; 0,2; 1,2	remove cell; return true
(1,2) / 3	matched C	0,0; 0,1; 0,2	remove cell; return true
(0,2) / 2	matched C	0,0; 0,1	remove cell; return true
(0,1) / 1	matched B	0,0	remove cell; return true
(0,0) / 0	matched A	empty	remove cell; return true
done	all six letters matched	empty	board unchanged; return true

Complexity Analysis

Time Complexity

O(mn \cdot 3^L)

Space Complexity

O(mn+L)

Let m and n be board dimensions and L the word length. The initial length guard takes constant time. Otherwise each of mn starts tries at most four first moves and at most three new moves thereafter, since the parent cell is already used. Rejected probes cost constant work, giving O(mn times 3^L) worst-case time for both approaches. Java allocates one O(mn) visited grid and reuses it after cleanup. Python and JavaScript use path sets of at most L cells with expected constant-time operations, so their auxiliary space is O(L); the displayed O(mn+L) bound covers all three languages. The stack is O(L). The Boolean return uses constant output space. These are bounds, not claims that every input explores all paths.

Code

Solution.java

1class Solution {2    public boolean exist(char[][] board, String word) {3        int m = board.length;4        int n = board[0].length;5        if (word.length() > board.length * board[0].length) return false;6        boolean[][] visited = new boolean[m][n];7        for (int r = 0; r < m; r++) {8            for (int c = 0; c < n; c++) {9                if (dfs(board, word, r, c, 0, visited)) {10                    return true;11                }12            }13        }14        return false;15    }16
17    private boolean dfs(char[][] board, String word, int r, int c, int i, boolean[][] visited) {18        // The previous frame already matched the final letter; no extra cell is consumed.19        if (i == word.length()) {20            return true;21        }22        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {23            return false;24        }25        if (visited[r][c] || board[r][c] != word.charAt(i)) {26            return false;27        }28        visited[r][c] = true;29        boolean found = dfs(board, word, r + 1, c, i + 1, visited)30                || dfs(board, word, r - 1, c, i + 1, visited)31                || dfs(board, word, r, c + 1, i + 1, visited)32                || dfs(board, word, r, c - 1, i + 1, visited);33        // Always restore the parent state, including when short-circuit search succeeded.34        visited[r][c] = false;35        return found;36    }37}

Hints

Hint 1

Treat each cell as a graph node with only its four side neighbors; the current path must match a prefix of the word.

Hint 2

Mark only cells in the current path, then unmark on return so other paths may use them.

Hint 3

Save the Boolean result before cleanup. A marker outside the legal alphabet lets the board carry the path record without a separate grid.

Edge Cases

A word longer than all m times n cells can never fit and should return false at once.
A one-cell board matches only a one-letter word equal to that cell.
Repeated letters such as ABCB only pass when distinct cells supply each occurrence.

Common Mistakes and Interview Tips

Forgetting to restore the stamped cell after the recursive calls, which blocks valid paths that cross it later.
Reading board[r][c] before the bounds check, which crashes on edge cells instead of returning false.
Reusing one visited record across start cells without clearing it, which hides words that begin later in the scan.
Returning immediately after a successful child before restoring the current mark leaves the caller board corrupted.
Treating uppercase and lowercase letters as interchangeable or allowing diagonal moves violates the path rules.
Claiming the visited approach must branch four ways at every depth: it also forbids returning to its parent, so both searches share the same worst-case exponential bound.

Key Takeaway

Grid path problems become graph searches by treating each cell as a node with four neighbours, and marking plus unmarking in place keeps backtracking memory tight.