Word Search

How it works

We want to check if the word can be formed by moving up/down/left/right in the grid, using each cell at most once in a single path.

Instead of keeping a separate visited matrix (extra space), we temporarily mark the current cell as used by replacing its character with a special value (like '#'). This means:

• If we ever see '#', we know this cell is already in our current path → we can't reuse it.
• After exploring from that cell, we restore the original character (this is the "backtrack" step), so other paths can use it.

So the idea is:

• Try every cell as a starting point.
• Do DFS to match the word character by character.
• Mark → explore neighbors → unmark.

Steps

1. Let ROWS, COLS be grid size.
2. Define dfs(r, c, i) meaning: "Can we match word[i...] starting from cell (r, c)?"
3. Base case: if i == len(word), we matched all characters → return true.
4. Fail cases: if out of bounds, current cell doesn't match word[i], or cell is already used ('#') → return false.
5. Mark the cell as used (set it to '#').
6. Try DFS in 4 directions with i + 1.
7. Restore the cell back to its original character (backtrack).
8. Run dfs(r, c, 0) from every cell (r, c). If any returns true, answer is true; otherwise false.

Complexity

• Time complexity: O(m * 4 ^ n)
• Space complexity: O(n)

Where m is the number of cells in the board and n is the length of the word.

Things to watch for

Not Restoring the Cell After Backtracking

When marking a cell as visited by changing its value (e.g., to '#'), forgetting to restore the original character after exploring all neighbors will permanently modify the board. This causes other paths starting from different cells to incorrectly treat valid cells as already visited.

Checking Visited Before Matching Character

Placing the visited check before the character match check can cause subtle bugs. If a cell is marked visited with a special character like '#', comparing board[r][c] != word[i] will correctly fail. However, if using a separate visited structure, the order of checks matters for correctness and clarity.

Forgetting to Match the First Character Before DFS

Starting DFS from every cell without first checking if board[r][c] == word[0] wastes time exploring paths that cannot possibly match the word. While not incorrect, this optimization significantly improves performance on large boards.

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        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
                word[i] != board[r][c] or board[r][c] == '#'):
                return False

            board[r][c] = '#'
            res = (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] = word[i]
            return res

        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        return False

class Solution {
public:
    int ROWS, COLS;

    bool exist(vector<vector<char>>& board, string word) {
        ROWS = board.size();
        COLS = board[0].size();

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (dfs(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    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 >= ROWS || c >= COLS ||
            board[r][c] != word[i] || board[r][c] == '#') {
            return false;
        }

        board[r][c] = '#';
        bool res = 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] = word[i];
        return res;
    }
};