Word Search

Mediumbacktrackingmatrixdepth-first-search
Category: Backtracking
Companies that ask this question:
AmazonFacebookGoogleMicrosoftBloomberg
LeetCode →NeetCode →

Approach

Word Search

Problem Statement

Given an m x n grid of characters board 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

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

Intuition

Grid Backtracking: Explore paths in 4 directions (up, down, left, right).

Approach:

  1. Find starting position (first letter)
  2. DFS from that position
  3. Mark visited cells (to avoid reuse)
  4. Backtrack if path doesn't work

Key: Temporarily mark cells as visited during exploration.

Pattern Recognition

This is a Grid Backtracking problem:

  • 2D grid traversal
  • Path exploration
  • State restoration (unmark visited)

Approach

def backtrack(row, col, index):
  if index == len(word):
    return True  # Found complete word

  if out_of_bounds or board[row][col] != word[index]:
    return False

  # Mark as visited
  temp = board[row][col]
  board[row][col] = '#'

  # Explore 4 directions
  found = (backtrack(row+1, col, index+1) or
           backtrack(row-1, col, index+1) or
           backtrack(row, col+1, index+1) or
           backtrack(row, col-1, index+1))

  # Restore cell
  board[row][col] = temp
  return found

Complexity Analysis

  • Time: O(m × n × 4^L) where L = word length

    • Try all cells: m × n
    • Each cell: 4 directions, depth L

  • Space: O(L) recursion depth

Solution

java
1class Solution {
2    public boolean exist(char[][] board, String word) {
3        int rows = board.length;
4        int cols = board[0].length;
5
6        // Try starting from each cell
7        for (int r = 0; r < rows; r++) {
8            for (int c = 0; c < cols; c++) {
9                if (backtrack(board, word, r, c, 0)) {
10                    return true;
11                }
12            }
13        }
14
15        return false;
16    }
17
18    private boolean backtrack(char[][] board, String word, int row, int col, int index) {
19        // Found complete word
20        if (index == word.length()) {
21            return true;
22        }
23
24        // Check bounds and character match
25        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
26            board[row][col] != word.charAt(index)) {
27            return false;
28        }
29
30        // Mark as visited
31        char temp = board[row][col];
32        board[row][col] = '#';
33
34        // Explore 4 directions
35        boolean found = backtrack(board, word, row + 1, col, index + 1) ||
36                       backtrack(board, word, row - 1, col, index + 1) ||
37                       backtrack(board, word, row, col + 1, index + 1) ||
38                       backtrack(board, word, row, col - 1, index + 1);
39
40        // Restore cell (backtrack)
41        board[row][col] = temp;
42        return found;
43    }
44}
45
Loading visualizer...