Matrix word search (grid DFS/backtracking)

O(mn*4^L)

From every cell, DFS tries to match the word letter by letter through up-down-left-right neighbors, marking a cell taken and restoring it on the way back if that path fails. It's backtracking where the grid itself is the decision tree.

Signals

does the word exist as a path on the boardtrace letters through adjacent cells, no reuseDFS with backtracking on a gridmark a cell as visited, then undo it

Template

function exist(board, word) {
    const rows = board.length, cols = board[0].length;
    function dfs(r, c, i) {
        if (i === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) return false;
        const tmp = board[r][c];
        board[r][c] = "#";
        const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) ||
                      dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
        board[r][c] = tmp;
        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;
}

Looks similar, isn't

Backtracking: Plain backtracking explores a decision list, like which subset or permutation to build next. Grid word search is the same choose/explore/undo loop but the grid IS the decision list: at each cell you try up to four neighbor directions, mark the cell taken, and restore it on the way back out.

grid up to ~6x6..12x12 and word length L up to ~10, DFS with 4 branches per step from every start cell -> O(mn * 4^L): backtracking dominates, not the grid size alone.

Learn this pattern