76.Word Search

MediumBlind 75Backtracking · 6/9

Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word must be built from letters of sequentially adjacent cells, where adjacent means horizontally or vertically neighbouring. The same cell may not be used more than once in a single word.

Examples

Input:  board = [["A","B","C","E"],
                 ["S","F","C","S"],
                 ["A","D","E","E"]], word = "ABCCED"
Output: true
Explanation: A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(2,2) → D(2,1).

Input:  same board, word = "SEE"
Output: true

Input:  same board, word = "ABCB"
Output: false
Explanation: The only B is at (0,1) and it cannot be reused.

Constraints

m == board.length, n == board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consist of only lowercase and uppercase English letters.

💡 Key Insight

Try every cell as a starting point and run a DFS that matches one character per step, moving in 4 directions. A cell may appear only once on the current path, so mark it as visited while it is on the path and unmark it when backtracking — other paths may legitimately use it. Marking in place (overwrite with '#') avoids an extra visited array, and a quick character-count check can reject impossible words before any search.

Backtracking with a Visited Array

SpaceO(m · n) for visited plus O(L) recursion depth.

Intuition

From each cell whose letter equals word[0], recursively look for word[1] among the 4 neighbours, and so on. A separate boolean[][] visited keeps track of the cells on the current path.

Algorithm

For each cell (r, c): if dfs(r, c, 0) returns true, return true.
dfs(r, c, k):
- If k == word.length(), return true (all characters matched).
- If out of bounds, visited[r][c], or board[r][c] != word[k], return false.
- Mark visited[r][c] = true.
- Recurse into the 4 neighbours with k + 1; if any is true, the answer is true.
- Unmark visited[r][c] = false and return the result.
Return false.

Visualization

word = "ABCCED"

A B C E        step 0: A at (0,0)
S F C S        step 1: B at (0,1)
A D E E        step 2: C at (0,2)
               step 3: C at (1,2)  (going right to E(0,3) fails)
               step 4: E at (2,2)
               step 5: D at (2,1)  -> k == 6, found

Code

java

class Solution {
    private char[][] board;
    private String word;
    private boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        this.visited = new boolean[board.length][board[0].length];
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                if (dfs(r, c, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(int r, int c, int k) {
        if (k == word.length()) return true; // every character matched
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
        if (visited[r][c] || board[r][c] != word.charAt(k)) return false;

        visited[r][c] = true;
        boolean found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1)
                || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
        visited[r][c] = false; // backtrack: free the cell for other paths
        return found;
    }
}

Complexity

Time: O(m · n · 4 · 3^(L-1)) — L = word.length(); from each start the first step has 4 directions and every later step at most 3 (it cannot go back).
Space: O(m · n) for visited plus O(L) recursion depth.

In-Place Marking with PruningOptimal

TimeO(m · n · 3^L) worst caseSpaceO(L)

Intuition

Two improvements on the same search:

In-place marking: temporarily overwrite board[r][c] with '#' while it is on the path. It can never match a letter, so it acts as "visited" without extra memory; restore it on the way back.
Pruning before search: if the board does not contain enough of some letter (e.g. word needs three Es but the board has two), return false immediately. Also, if the last letter of word is rarer on the board than the first, reverse the word — starting from the rarer end generates far fewer starting branches.

Algorithm

Count letters on the board and in word; if any letter of word is in short supply, return false.
If count[last letter] < count[first letter], reverse word.
For every cell, run dfs(r, c, 0):
- Return true when k == L.
- Return false if out of bounds or board[r][c] != word[k].
- Save ch = board[r][c], set board[r][c] = '#'.
- Recurse into the 4 neighbours; restore board[r][c] = ch.

Visualization

flowchart TD
    S["start (0,0)='A' k=0"] --> B["(0,1)='B' k=1"]
    S -.->|"down"| X1["(1,0)='S' ≠ B"]
    B --> C1["(0,2)='C' k=2"]
    C1 -.->|"right"| X2["(0,3)='E' ≠ C"]
    C1 --> C2["(1,2)='C' k=3"]
    C2 -.->|"right"| X3["(1,3)='S' ≠ E"]
    C2 --> E1["(2,2)='E' k=4"]
    E1 --> D1["(2,1)='D' k=5"]
    D1 --> F["k = 6 = L → true"]

Code

java

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        if (word.length() > m * n) return false;

        // Pruning 1: the board must contain enough of every letter
        int[] boardCount = new int[128];
        int[] wordCount = new int[128];
        for (char[] row : board) {
            for (char ch : row) boardCount[ch]++;
        }
        for (char ch : word.toCharArray()) {
            if (++wordCount[ch] > boardCount[ch]) return false;
        }

        // Pruning 2: start from the rarer end of the word
        char[] w = word.toCharArray();
        if (boardCount[w[w.length - 1]] < boardCount[w[0]]) {
            for (int i = 0, j = w.length - 1; i < j; i++, j--) {
                char tmp = w[i];
                w[i] = w[j];
                w[j] = tmp;
            }
        }

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (dfs(board, w, r, c, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] w, int r, int c, int k) {
        if (k == w.length) return true;
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
        if (board[r][c] != w[k]) return false; // also rejects '#' (cell on current path)

        char saved = board[r][c];
        board[r][c] = '#'; // mark as used
        boolean found = dfs(board, w, r + 1, c, k + 1) || dfs(board, w, r - 1, c, k + 1)
                || dfs(board, w, r, c + 1, k + 1) || dfs(board, w, r, c - 1, k + 1);
        board[r][c] = saved; // restore for other paths
        return found;
    }
}

Complexity

Time: O(m · n · 3^L) worst case — same bound, but the pre-checks cut most hopeless inputs in O(m · n + L).
Space: O(L) — recursion depth only; the board is restored after the search.

Complexity Comparison

Approach	Time	Space
Backtracking + visited[][]	O(m · n · 3^L)	O(m · n + L)
In-place Marking + Pruning	O(m · n · 3^L) worst, pruned	O(L)

Common Pitfalls

Not unmarking the cell after exploring it — a cell used by a failed branch becomes permanently blocked for later paths.
Checking k == word.length() after the bounds check — a word ending at the board edge then wrongly fails when the next call goes out of bounds.
Returning as soon as one direction fails instead of trying all four.
Forgetting to restore board[r][c] before returning true leaves the input corrupted (harmless on LeetCode, a bug elsewhere) — the code above restores before returning.