Word Search Grid Backtracking DSA Solution - Study Chapter | QuizMaker
Word Search explained with path brute force, optimized grid backtracking, dry run, edge cases, complexity, and Python, C++, Java code.
- Read
- 12m
- Type
- Chapter
- Access
- Free
Course
DSA Course: Interview Patterns and Problem Solving
Topic
Module 11: Recursion & Backtracking
Learning Outcome
After this lesson, you should be able to mark a grid cell as used during one path and restore it for future paths.
Problem Statement
Given a board and a word, return true if the word exists by moving horizontally or vertically through adjacent cells without reusing a cell.
| Input | Output | Why |
|---|---|---|
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" | true | A path A -> B -> C -> C -> E -> D exists using adjacent cells. |
Brute Force Approach
Generate paths without checking the next required character early. This explores too many impossible paths.
Optimized Approach
Start DFS from every matching cell. Stop on boundary, mismatch, or reused cell, and restore the cell after exploring.
Exact Pseudocode
exists(row, col, index):
if index == word.length:
return true
if out of bounds or board[row][col] != word[index]:
return false
save cell and mark used
found = search four neighbors for index + 1
restore cell
return found
for each cell:
if exists(cell, 0):
return true
return false
Reference Code
class Solution:
def exist(self, board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True
if r < 0 or c < 0 or r == rows or c == cols or board[r][c] != word[i]:
return False
saved = board[r][c]
board[r][c] = "#"
found = (
dfs(r + 1, c, i + 1) or
dfs(r - 1, c, i + 1) or
dfs(r, c + 1, i + 1) or
dfs(r, c - 1, i + 1)
)
board[r][c] = saved
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False
class Solution {
public:
bool dfs(vector<vector<char>>& board, string& word, int r, int c, int i) {
if (i == word.size()) return true;
if (r < 0 || c < 0 || r == board.size() || c == board[0].size() || board[r][c] != word[i]) return false;
char saved = board[r][c];
board[r][c] = '#';
bool 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] = saved;
return found;
}
bool exist(vector<vector<char>>& board, string word) {
for (int r = 0; r < board.size(); r++) {
for (int c = 0; c < board[0].size(); c++) {
if (dfs(board, word, r, c, 0)) return true;
}
}
return false;
}
};
class Solution {
public 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 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 saved = board[r][c];
board[r][c] = '#';
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] = saved;
return found;
}
}
Sample Dry Run
| Step | State | Result |
|---|---|---|
| Start A | board[0][0] matches word[0] | Mark A used |
| Move to B | Right neighbor matches word[1] | Continue path |
| Continue C,C,E,D | Each step matches next character | index reaches word length |
| Return | Base case true | Word exists |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(rows * cols * 4^wordLength) | Each cell can start a DFS and each step can branch up to four ways. |
| Space | O(wordLength) | The recursion depth is at most the word length. |
Edge Cases
- The same cell cannot be reused in one path.
- Only horizontal and vertical moves are allowed.
- Restore the cell after each path attempt.
Interview Checklist
- Check boundary and character mismatch before marking.
- Mark the current cell as used for this path.
- Restore the cell before returning.
FAQs
Why restore the cell?The same cell may be needed in a different path starting elsewhere.
Why mark in-place?It avoids an extra visited matrix while still preventing reuse in the current path.
What is the core pattern?Grid backtracking with temporary marking.
Tags
- dsa
- recursion-backtracking
- grid backtracking