0079. Word Search.md

LeetCode 79 — Word Search (Backtracking)

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();

        function<bool(int,int,int)> backtrack = [&](int i, int j, int k) {
            if(i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word[k]) return false;
            if(k == word.size() - 1) return true;
            char val = board[i][j];
            board[i][j] = '.';

            bool res = backtrack(i + 1, j, k + 1)
            || backtrack(i - 1, j, k + 1)
            || backtrack(i, j + 1, k + 1)
            || backtrack(i, j - 1, k + 1);

            board[i][j] = val;
            return res;
        };

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(backtrack(i, j, 0)) return true;
            }
        }

        return false;
    }
};

---

Problem Summary

Given an m x n grid of characters and a string word, determine whether the word exists in the grid.

Rules:

• The word must be constructed from sequentially adjacent cells (up, down, left, right).
• The same cell cannot be used more than once in a single path.

---

Core Idea

This is a classic backtracking / DFS on a grid problem.

Key observations:

• Any cell can be a starting point.
• At each step, we try to match the current character and explore 4 directions.
• We must mark the current cell as visited to avoid reuse, then restore it after recursion (backtracking).

---

Algorithm

1. Iterate through every cell in the board as a potential starting point.
2. Use DFS (backtrack) to try matching word[k] starting from (i, j).
3. Base cases:
   • Out of bounds or character mismatch → return false
   • Matched the last character → return true
4. Mark the cell as visited (temporarily).
5. Recursively explore 4 directions.
6. Restore the cell value before returning.

---

---

Why Backtracking Works Here

• Each recursive call represents choosing one path.
• If a path fails, we undo the choice and try another direction.
• As soon as one valid path matches the full word, we stop early.

---

Time Complexity

O(M × N × 4ᴸ)

• M × N: possible starting positions
• 4: branching factor (up, down, left, right)
• L: length of the word

---

Space Complexity

O(L)

• Maximum recursion depth equals the word length
• Board is modified in-place (no extra visited matrix)

---

Takeaway

This problem is a textbook example of:

• DFS on a grid
• Backtracking with state restoration
• Early termination once a valid path is found