Algorithm Day61 - Word Search (lc-79)

Posted on Edited on In , Views:

🧩 Problem Description

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

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

💬 Examples

Example 1

1
2
3
4
Input: board = [["A","B","C","E"],
                ["S","F","C","S"],
                ["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2

1
2
3
4
Input: board = [["A","B","C","E"],
                ["S","F","C","S"],
                ["A","D","E","E"]], word = "SEE"
Output: true

Example 3

1
2
3
4
Input: board = [["A","B","C","E"],
                ["S","F","C","S"],
                ["A","D","E","E"]], word = "ABCB"
Output: false

💡 Intuition

This is a classic backtracking on a grid problem.

  • Try to start from every cell that matches word[0].
  • From each start, run DFS with index k into word.
  • Mark the current cell as visited during the recursion to avoid reuse.
  • Backtrack (unmark) when returning.

A tiny optimization: early-exit if remaining occurrences of a letter are impossible (optional).

🔢 Java Code (Backtracking + In-place Visited)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }

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

        char temp = b[i][j];
        b[i][j] = '#'; // mark visited

        boolean found = dfs(b, w, i + 1, j, k + 1) ||
                        dfs(b, w, i - 1, j, k + 1) ||
                        dfs(b, w, i, j + 1, k + 1) ||
                        dfs(b, w, i, j - 1, k + 1);

        b[i][j] = temp; // unmark
        return found;
    }
}

⏱ Complexity Analysis

Let L = word.length, m x n = board size.

  • Time: O(m × n × 4^L) in the worst case (tight upper bound). Pruning from mismatches helps in practice.
  • Space: O(L) recursion depth; in-place marking avoids extra visited arrays.

✍️ Summary

  • Backtracking with DFS from any matching start cell.
  • Use in-place marking to avoid revisiting the same cell in a path.
  • Return true immediately when k == L.

Related problems

  • lc-212 — Word Search II (Trie + backtracking)
  • lc-200 — Number of Islands
  • lc-79 variations — diagonal/knight moves (custom)