Problem statement
Return whether a word can be read through horizontally or vertically adjacent cells of a character board. Read its letters in order and use a cell at most once within the matching path. Different cells containing the same letter are allowed.
LeetCode Word Search permits 1–6 rows and columns, words of length 1–15, and uppercase/lowercase English letters. Matching is case-sensitive. There are no diagonal moves or jumps. This asks about one word, not Word Search II’s list of words.
Constraints & requirements
- CONTRACT
- LeetCode: 1–6 rows/columns, word length 1–15, uppercase/lowercase English letters. Search is case-sensitive. Preserve the board; this is one-word existence, not Word Search II.
Examples 3 test cases
Example 1 Case 1
- Input
rows=["ABCE","SFCS","ADEE"]; word="ABCCED"- Output
true
Path (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1) spells the word.
Example 2 Case 2
- Input
rows=["ABCE","SFCS","ADEE"]; word="SEE"- Output
true
The two E letters occupy different cells, so both may be used.
Example 3 Case 3
- Input
rows=["ABCE","SFCS","ADEE"]; word="ABCB"- Output
false
The tempting route would need to reuse the B cell; this is not allowed.
Hints Optional
01Hint 1
Try every cell as a possible start; matching the first letter alone is not success.
02Hint 2
Track both the next letter index and cells used by the active path.
03Hint 3
Mark before exploring four neighbors, then unmark even when short-circuit OR finds a successful child.
How to think before coding
A call means board[row][col] must match word[index]. Check bounds, reservation and letter before marking. Only after the final letter matches is the word found. The visited array belongs to the active path, so unmark even after a successful child before returning. That preserves the board and allows independent starts; identical letters in different cells are not a conflict.
Brute force and the improvement
Try every start cell and all four-direction move sequences long enough to spell the word, validating letters, boundaries and no reused cell after constructing each candidate. A loose O(R·C·4^L·L) bound includes checking length-L paths; working path storage is O(L). Prefix DFS rejects a wrong letter or reserved cell immediately, avoiding the rest of that sequence. It can stop after one match, but still has exponential path choices in the worst case.
Intuition: reserve cells, not letters
On rows ABCE / SFCS / ADEE, ABCCED follows six adjacent cells. The two C letters occupy different positions. A set of used letters would incorrectly reject them; we must remember used coordinates.
For ABCB, the obvious A→B→C route would need to return to the same B cell. A cell cannot supply two positions of this word, so that continuation fails.
The recursive state combines the current cell, the next word index, and reservations on the active path. A globally discovered-cell mark is wrong: a cell used by a failed path may still belong to a successful path from another start.
Algorithm
- Try every board cell as a possible start.
- Return true after all word letters have already matched.
- Otherwise reject an out-of-bounds, already-reserved or mismatching cell.
- Reserve the matching cell and recurse with the next word index in four directions.
- Combine child results with short-circuit OR.
- Release this cell before returning the result, including after success.
The base case precedes the bounds check because a completed word needs no extra cell. Reaching index==word.length means the preceding call already matched its final letter; it is not accepting an unmatched outside-grid letter.
Java solution
A boolean visited matrix records only cells on the current path. The helper never mutates board letters. Empty-word/empty-board behavior is defensive; the linked problem specifies nonempty inputs.
import java.util.*;
class Solution {
public static boolean exist(char[][] board, String word) {
if (word.isEmpty()) return true; // Defensive extension: an empty sequence needs no cells.
if (board.length == 0 || board[0].length == 0) return false;
boolean[][] visited = new boolean[board.length][board[0].length]; // Active path, not global discovery.
for (int row = 0; row < board.length; row++) for (int col = 0; col < board[0].length; col++) {
if (wordPath(board, word, 0, row, col, visited)) return true; // Try EVERY possible start.
}
return false; // All starts failed; matching first letters alone is insufficient.
}
private static boolean wordPath(char[][] board, String word, int index, int row, int col, boolean[][] visited) {
if (index == word.length()) return true; // All letters already matched; no extra cell is needed.
if (row < 0 || row >= board.length || col < 0 || col >= board[0].length
|| visited[row][col] || board[row][col] != word.charAt(index)) return false;
visited[row][col] = true; // This cell cannot be reused by descendants of this path.
boolean found = wordPath(board, word, index + 1, row + 1, col, visited)
|| wordPath(board, word, index + 1, row - 1, col, visited)
|| wordPath(board, word, index + 1, row, col + 1, visited)
|| wordPath(board, word, index + 1, row, col - 1, visited); // Orthogonal moves only.
visited[row][col] = false; // Restore even after success; do not leave cells marked for later use.
return found; // Short-circuit OR asks whether ANY complete path exists.
}
public static void main(String[] args) {
char[][] board = {"ABCE".toCharArray(), "SFCS".toCharArray(), "ADEE".toCharArray()};
System.out.println(exist(board, "ABCCED")); // true
System.out.println(exist(board, "ABCB")); // false; the same board remains usable.
}
}The invocation prints true for ABCCED and false for ABCB using the same unchanged board. Equal letters in different cells remain independent choices.
Recursion tree and dry run

Read the text transcript
Follow the Java, step by step
Example: rows = ["ABCE","SFCS","ADEE"], word = "ABCB"
What to track: index is the next required letter; row/col identify the candidate cell. visited reserves only the current path. This failure example exposes the tempting repeated-B bug.
-
Match A at the first start
Java operationvisited[row][col] = true;Stateindex = 0; cell (0,0) matches A; visited = {(0,0)}Matching the first character is not complete success. The child must match B next.
-
Reach B, then C
Java operationwordPath(board, word, index + 1, row, col + 1, visited)Stateafter earlier failed neighbor checks: match B at (0,1), then C at (0,2); index = 2The Java neighbor order is down, up, right, left. This row summarizes the rejected neighbors before each successful right move.
-
Reject the reused B cell
Java operationvisited[row][col]StateC needs index = 3, letter B; left neighbor (0,1) is B but is already visitedThe other C neighbors are out of bounds or contain the wrong letter. All four child attempts return false; a path cannot reuse its B.
-
Unmark C before returning
Java operationvisited[row][col] = false;StateC frame found = false; (0,2) released; waiting B frame resumesThe marker is released on return. It must not remain reserved for another start or sibling path.
-
Unwind the failed path
Java operationreturn found;StateB and A try remaining neighbors, find no complete continuation, unmark themselves and return falseThe start loop continues. The other A at (2,0) has no adjacent B, and all other starts fail their first-letter check.
-
Report exhausted starts
Java operationreturn false;Stateno call reached index == word.length(); all visited entries are falseA successful word would return true at that base case. Restoration still occurs while successful frames return, because visited is cleared before return found.
Final result: false; the board remains unchanged and all visited marks are cleared.
col 0 1 2 3
row 0 A B C E
row 1 S F C S
row 2 A D E E
successful path for ABCCED:
(0,0) A → (0,1) B → (0,2) C
↓
(1,2) C
↓
(2,1) D ← (2,2) E| Matched cell | Word index | Next required letter |
|---|---|---|
| (0,0), A | 0 | B |
| (0,1), B | 1 | C |
| (0,2), C | 2 | C |
| (1,2), C | 3 | E |
| (2,2), E | 4 | D |
| (2,1), D | 5 | None; the word is complete |
This table follows a successful path, not every rejected neighbor. After the final letter, true returns upward. Every waiting caller still executes visited[row][col] = false before returning its own true result.
For ABCB, the state at C (0,2) requires B next. The B at (0,1) is reserved, the other neighbors do not match, and the branch returns false. Undo makes those cells available for later attempts, but does not permit reuse within the failed active route.
Why store the OR result before returning?
Writing an immediate return for the OR would skip the following restoration line. Storing found lets the code unmark its cell after both successful and unsuccessful searches. Short-circuiting still avoids unnecessary sibling calls once a child succeeds.
Why it works
The active path matches exactly the consumed prefix of the word, is orthogonally connected, and has no repeated cell. Every accepted matching cell preserves those properties. Reaching the word’s length therefore proves a valid path.
Every start and every legal next neighbor is tried unless success is already known. Any existing word path has such a start and sequence of choices, so it is found. Restoring reservations ensures earlier attempts do not remove later candidates.
Complexity and alternative approaches
For R rows, C columns and word length L, a conservative time bound is O(RC·4^L). After the first move, the immediately previous cell is forbidden, giving a tighter branching intuition of three onward directions. Character mismatches and other visited cells prune further, but the search can still be exponential.
The visited matrix uses O(RC); recursive frames use O(L). Thus this implementation’s auxiliary space is O(RC+L), not merely O(L). An in-place sentinel can remove the extra matrix, but must restore letters reliably and reserve a value outside the input alphabet.
Useful pruning includes rejecting L>RC or insufficient letter frequencies. Starting from the rarer end of the word can also reduce attempts because reversing an undirected path preserves adjacency. These are optional performance improvements, not substitutes for the no-reuse rule. A trie is useful for many-word search, not necessary for this one-word contract.
Common mistakes
- Marking used letters instead of used coordinates.
- Allowing diagonal movement or reuse of the same B in ABCB.
- Trying only the first cell that matches the first letter.
- Leaving cells reserved after a failed start.
- Returning directly before the cleanup line.
- Claiming a board-wide visited matrix is constant auxiliary space.