Word Search (LC 79)

Pattern: Backtracking DFS on grid
Difficulty: Medium
Key Concept: From each cell, DFS along valid neighbors matching the next character; mark visited on the path and undo (backtrack) when returning so other branches can reuse cells.

Problem Statement

Given m x n grid board of letters and a string word, return true if word exists as a path of horizontally or vertically adjacent cells without reusing the same cell twice.

Input: char[][] board, String word
Output: boolean

---

1. Algorithm & Pseudocode

Brute force

From every cell, generate all simple paths up to length L (no repeat), check against word — factorial/exponential without pruning.

Optimal

Pruned backtracking

for each cell (r,c):
  if dfs(r,c,0): return true
return false

dfs(r,c,k):   // match word[k..]
  if k == word.length: return true
  if out of bounds or board[r][c] != word[k]: return false

  temp = board[r][c]
  board[r][c] = '#'   // mark visited

  for each neighbor (nr,nc):
    if dfs(nr,nc,k+1): return true

  board[r][c] = temp   // unmark
  return false

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Choice at each step: which neighbor extends the partial match.
• Why mutate board: O(1) visited marking; restore on exit so other DFS starts see a clean board.
• Pruning: wrong letter or boundary → immediate false saves huge work vs enumerating all paths.
• Complexity note: worst-case still exponential in board size, but constraints and pruning make it pass; interview discussion may mention Trie batch search for many words (different problem).

---

3. The Dry Run

board:

A B C E
S F C S
A D E E

word = "ABCCED"

Start (0,0) A → (0,1) B → (0,2) C → (1,2) C → (2,2) E → (2,1) D — success.

k	pos	action
0	(0,0)	match A, mark
1	(0,1)	match B
2	(0,2)	match C
3	(1,2)	match C
4	(2,2)	match E
5	(2,1)	match D, k+1 == len → true

Backtrack unwinds marks after success.

---

4. Java Solution

Brute Force

Conceptually enumerate all paths — not implemented at scale; the DFS without pruning below is already better but shows contrast:

// Naive: try all directions without early char check ordering — same structure as optimal
// but without fail-fast; still exponential. Optimal adds pruning + visited bitmask.

Practical “weaker” variant: allocate boolean[m][n] visited instead of board mutation — same time class, O(mn) extra space.

class SolutionBrute {
    private static final int[][] D = {{1,0},{-1,0},{0,1},{0,-1}};

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

    private boolean dfs(char[][] b, String w, int k, int r, int c, boolean[][] vis) {
        if (k == w.length()) return true;
        if (r < 0 || r >= b.length || c < 0 || c >= b[0].length) return false;
        if (vis[r][c] || b[r][c] != w.charAt(k)) return false;

        vis[r][c] = true;
        for (int[] d : D) {
            if (dfs(b, w, k + 1, r + d[0], c + d[1], vis)) return true;
        }
        vis[r][c] = false;
        return false;
    }
}

Time: exponential in worst case, Space: O(mn) visited + O(L) stack.

Optimal

In-place marking

class Solution {
    private static final int[][] D = {{1,0},{-1,0},{0,1},{0,-1}};

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

    private boolean dfs(char[][] b, String w, int k, int r, int c) {
        if (k == w.length()) return true;
        if (r < 0 || r >= b.length || c < 0 || c >= b[0].length) return false;
        if (b[r][c] != w.charAt(k)) return false;

        char tmp = b[r][c];
        b[r][c] = '#';
        for (int[] d : D) {
            if (dfs(b, w, k + 1, r + d[0], c + d[1])) {
                b[r][c] = tmp;
                return true;
            }
        }
        b[r][c] = tmp;
        return false;
    }
}

Time: O(m·n·4^L) worst-case bound (L = word length); Space: O(L) recursion depth.

---

5. The “Java vs. Others” Edge

• word.charAt(k) in loop — Java strings are immutable; for hot paths, char[] w = word.toCharArray() avoids repeated bounds checks (micro-optimization).
• Board restoration must happen on both success and failure paths (shown).
• Prune board cells not matching first char before DFS to reduce calls.

---

6. Complexity Summary

Approach	Time	Space	Notes
Extra vis[][]	O(m·n·4^L) worst	O(mn) + O(L)	Does not mutate input
In-place # mark	O(m·n·4^L) worst	O(L) stack	Standard interview

---

ASCII: Path on grid (cannot reuse)

word = C A T

. C . .        Start at C, try neighbors for 'A':
. A T .   =>   only valid path continues to A then T
. . . .        Backtrack if neighbor letter wrong