Intermediate LevelData Structures & Algorithms
How do you solve the Word Search problem on a 2D grid using Backtracking?
ā Interview Prompt: Search for a word in a 2D character grid using DFS backtracking with visited marking.
Approach: For each cell matching word[0], initiate a DFS exploring all 4 directions. Mark cells as visited before recursing and unmark (backtrack) when returning.
ā¢
Time: $O(M \times N \times 4^L)$ where $L$ = word length.
ā¢
Space: $O(L)$ recursion stack.
Key: Modify the grid in-place to mark visits (set to '#'), avoiding an extra visited matrix.
Code Implementation Example
typescript
function exist(board: string[][], word: string): boolean {
const rows = board.length, cols = board[0].length;
function dfs(r: number, c: number, idx: number): boolean {
if (idx === word.length) return true;
if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[idx])
return false;
const temp = board[r][c];
board[r][c] = '#'; // mark visited
const found =
dfs(r + 1, c, idx + 1) || dfs(r - 1, c, idx + 1) ||
dfs(r, c + 1, idx + 1) || dfs(r, c - 1, idx + 1);
board[r][c] = temp; // backtrack (unmark)
return found;
}
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (dfs(r, c, 0)) return true;
return false;
}š”Word Search DFS backtracking with in-place visited marking.
šÆ Interview Key Takeaway
Word Search exemplifies backtracking with in-place state modification. Backtrack by restoring the cell value after each DFS branch.
#DSA#Backtracking#DFS#Grid#Intermediate
Back to all Data Structures & Algorithms Questionsā