Word Search

Problem Link

Problem: Word Search

Problem Statement

Given an m x n 2D board and a word, determine if the word exists in the grid.

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

Examples

Example 1
Input:

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]], 
word = "ABCCED"

Output: true

Example 2
Input:

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]], 
word = "SEE"

Output: true

Example 3
Input:

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]], 
word = "ABCB"

Output: false

Constraints

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

Intuition

We need to search for the given word in a matrix such that:

Characters must match in adjacent (up, down, left, right) directions.
Each character of the word must be used in order.
A cell can only be used once per word path.

This naturally leads to a backtracking solution where we:

Try every cell as a starting point.
Recursively explore all 4 directions.
Mark cells as visited and restore them after exploring (backtracking).

Approach (Backtracking)

For each cell in the grid, if the character matches the first character of the word:
- Call a recursive function to check if the rest of the word can be found starting from that cell.
The recursive function (find) checks:
- If the current cell is out of bounds or already visited.
- If the character at the current cell matches the current character in the word.
- If we’ve reached the end of the word (idx == word.length()).
Temporarily mark the cell as visited (e.g., with a *) and explore its 4 neighbors.
Restore the cell (backtrack) after exploring.

Code (Java)

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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (find(i, j, m, n, word, 0, board)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean find(int i, int j, int m, int n, String word, int idx, char[][] board) {
        if (idx == word.length()) return true;

        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word.charAt(idx)) {
            return false;
        }

        char ch = board[i][j];
        board[i][j] = '*'; // mark visited

        boolean left = find(i, j - 1, m, n, word, idx + 1, board);
        boolean up = find(i - 1, j, m, n, word, idx + 1, board);
        boolean right = find(i, j + 1, m, n, word, idx + 1, board);
        boolean down = find(i + 1, j, m, n, word, idx + 1, board);

        board[i][j] = ch; // backtrack

        return left || up || right || down;
    }
}

Time and Space Complexity

Time Complexity: O(m * n * 4^L)
Where L is the length of the word, and m * n is the number of starting points.
At each step, we explore up to 4 directions.
Space Complexity: O(L)
Recursion depth can go up to the length of the word.

Dry Run

Input:

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]]
word = "ABCCED"

Start at (0,0): matches A
Move to (0,1): matches B
Move to (0,2): matches C
Move to (1,2): matches C
Move to (1,1): matches E → incorrect
Backtrack and try (2,2): matches E
Move to (2,1): matches D → complete

Returns true.

Conclusion

This problem is a textbook application of DFS with backtracking in a 2D matrix. The use of in-place marking and recursive exploration of valid paths highlights how backtracking works efficiently in grid search problems.