Q19: How do you solve Word Search on a 2D Board using Recursion / Backtracking?
Iterate through matrix cells. When starting character matches, invoke DFS backtracking (backtrack(board, word, r, c, index)). Mark current cell as visited (e.g. board[r][c] = '#'), recursively explore 4-directional neighbors, and restore cell state (board[r][c] = temp) during back-step.
Word Search Backtracking Solution
public class WordSearch {
public static boolean exist(char[][] board, String word) {
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
if (dfs(board, word, r, c, 0)) return true;
}
}
return false;
}
private static boolean dfs(char[][] board, String word, int r, int c, int i) {
if (i == word.length()) return true;
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(i)) {
return false;
}
char temp = board[r][c];
board[r][c] = '#'; // Mark visited
boolean found = dfs(board, word, r + 1, c, i + 1) ||
dfs(board, word, r - 1, c, i + 1) ||
dfs(board, word, r, c + 1, i + 1) ||
dfs(board, word, r, c - 1, i + 1);
board[r][c] = temp; // Backtrack restore
return found;
}
}💡 Marks board cells temporarily during DFS search and restores state during backtracking steps.
Key Takeaways
- DFS recursive grid traversal with backtracking.
- Restoring visited state during back-stepping allows alternative paths to reuse board cells.
Knowledge Check
What is the purpose of board[r][c] = temp during the backtracking step?