Problem
Given an m × n grid of characters board and a string word, return true if the word exists in the grid. Otherwise, return false.The word must be formed from sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same cell cannot be used more than once in the same path.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]
word = "ABCCED"
+---+---+---+---+
| A | B | C | E |
+---+---+---+---+
| S | F | C | S |
+---+---+---+---+
| A | D | E | E |
+---+---+---+---+
Output
true A → B → C ↓ C ↓ E ← D Solution
This solution uses Backtracking to explore all possible paths starting from each cell in the grid.For each matching character, we recursively explore its four adjacent cells: up, down, left, and right. If the current cell does not match the required character or has already been used in the current path, that path is stopped.
Before exploring adjacent cells, the current cell is temporarily marked as visited. After the recursive calls return, its original value is restored. This backtracking step allows the cell to be used again when exploring a different path.
public boolean exist(char[][] board, String word) {
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[0].length; col++) {
if (backtrack(board, word, row, col, 0)) {
return true;
}
}
}
return false;
}
private boolean backtrack(char[][] board, String word,
int row, int col, int index) {
// All characters are matched.
if (index == word.length()) {
return true;
}
// Invalid position or character mismatch.
if (row < 0 || row >= board.length
|| col < 0 || col >= board[0].length
|| board[row][col] != word.charAt(index)) {
return false;
}
// Mark the current cell as visited.
char current = board[row][col];
board[row][col] = '#';
boolean found = backtrack(board, word, row + 1, col, index + 1)
|| backtrack(board, word, row - 1, col, index + 1)
|| backtrack(board, word, row, col + 1, index + 1)
|| backtrack(board, word, row, col - 1, index + 1);
// Restore the cell.
board[row][col] = current;
return found;
}
Complexity
For each cell, the algorithm may explore multiple paths to match the word. In the worst case, each recursive step can explore up to four directions, resulting in a time complexity ofO(m × n × 4L), where L is the length of the word.
The recursive call stack can grow up to the length of the word, resulting in
O(L) extra space.