Word Search Grid Backtracking DSA Solution - Study Chapter | QuizMaker

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.

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

Complexity

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

The same cell may be needed in a different path starting elsewhere.

It avoids an extra visited matrix while still preventing reuse in the current path.

Grid backtracking with temporary marking.

Tags

• dsa
• recursion-backtracking
• grid backtracking