Q22: Word Search (Backtracking)
Determine if a target word exists in a 2D board of letters by constructing adjacent character paths using Backtracking DFS.
2D Grid Backtracking Search
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
function backtrack(r, c, index) {
if (index === word.length) return true;
if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[index]) {
return false;
}
const temp = board[r][c];
board[r][c] = '#'; // Mark cell as visited
const found = backtrack(r + 1, c, index + 1) ||
backtrack(r - 1, c, index + 1) ||
backtrack(r, c + 1, index + 1) ||
backtrack(r, c - 1, index + 1);
board[r][c] = temp; // Backtrack / restore state
return found;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (backtrack(r, c, 0)) return true;
}
}
return false;
}💡 Explores neighbors recursively if character matches word[index]. Restores cell state (board[r][c] = temp) when returning so other path branches can reuse the cell.
Key Takeaways
- Backtracking recursively explores possibilities and reverts choice state upon reaching dead ends.
- Temporarily mark board cells (e.g.
'#') during exploration to prevent self-revisiting.
Knowledge Check
Why must board[r][c] be restored back to its original character value before returning from backtrack()?