You are given a 2D board of characters and a word.
Your task is to determine whether the word exists in the board.
A word exists if it can be constructed from sequentially adjacent cells.
Valid moves are only horizontal and vertical (no diagonal).
The same cell cannot be used more than once.
Understanding the Problem
Example:
Board:
A B C E
S F C S
A D E E
Word = “ABCCED”
Output = true
Explanation: The word is found by moving right, right, down, down, left.
Another example:
Word = “SEE”
Output = true
Word = “ABCB”
Output = false
You cannot reuse the same cell.
Approach (Explained in Simple Language)
This is a classic Depth-First Search (DFS) + Backtracking problem.
1. Try to start matching the word from every cell
The first character of the word may appear anywhere in the grid.
2. When a character matches, explore all four directions
Move up, down, left, right to try to match the next character.
3. Use backtracking to avoid reusing the same cell
When visiting a cell, temporarily mark it as used (e.g., store its value and replace with ‘#’).
Once the DFS for that path ends, restore the cell’s value.
4. If all characters match in sequence, return true
If all DFS attempts fail, return false.
This approach ensures we systematically check all possible paths.
Time complexity is manageable because backtracking stops early when mismatches occur.
Java Code
public class WordSearch {
public boolean exist(char[][] board, String word) {
int rows = board.length;
int cols = board[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (dfs(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int row, int col, int index) {
if (index == word.length()) {
return true;
}
if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
return false;
}
if (board[row][col] != word.charAt(index)) {
return false;
}
char temp = board[row][col];
board[row][col] = '#';
boolean found =
dfs(board, word, row + 1, col, index + 1) ||
dfs(board, word, row - 1, col, index + 1) ||
dfs(board, word, row, col + 1, index + 1) ||
dfs(board, word, row, col - 1, index + 1);
board[row][col] = temp;
return found;
}
public static void main(String[] args) {
WordSearch solution = new WordSearch();
}
}
Dry Run
Use the sample:
Board:
A B C E
S F C S
A D E E
Word = “ABCCED”
Start from each cell.
Step 1: Start at board[0][0] = ‘A’
Matches word[0] = ‘A’
Call DFS.
Path so far: A
Index = 1
Next char = ‘B’
Step 2: Check neighbors of (0,0)
Down → ‘S’ (no)
Up → out of bounds
Left → out of bounds
Right → ‘B’ (yes)
Move to (0,1)
Path: A B
Index = 2
Next char = ‘C’
Step 3: From (0,1) look for ‘C’
Right → ‘C’ at (0,2)
Path: A B C
Index = 3
Next char = ‘C’
Step 4: From (0,2) look for ‘C’ again
Down → ‘C’ at (1,2)
Path: A B C C
Index = 4
Next char = ‘E’
Step 5: From (1,2) look for ‘E’
Down → ‘E’ at (2,2)
Path: A B C C E
Index = 5
Next char = ‘D’
Wait, the word is ABCCED, so the last letter is D.
Step 6: From (2,2) look for ‘D’
Left → board[2][1] = ‘D’
Path: A B C C E D
Index = 6 → reached word.length()
Return true.
Why This Approach Works
DFS explores all possible valid paths from each character.
Backtracking ensures that:
cells are not reused
dead-end paths do not affect other searches
the board remains unchanged
This is the standard technique for grid-based pathfinding with constraints.