How do you solve Word Search?

Implement a DFS helper function that takes the current cell coordinates and the index of the character to match. The function returns true if the remaining substring can be matched starting from that cell. It checks boundary conditions, character match, and visited state. If valid, it marks the cell as visited, recursively explores all four adjacent directions for the next character, and backtracks by unmarking the cell. The main function iterates over all cells, invoking DFS from each as a potential start. If any DFS returns true, the word exists in the board.

What pattern does Word Search use?

The Pattern: DFS (Stateful Exploration with Backtracking) The Heuristic: When searching for a path with constraints on revisiting nodes, use DFS with explicit state tracking (visited set) and backtracking to explore all valid paths while pruning invalid ones efficiently.

Word Search — DFS

Q: What is the time complexity of Word Search?

O(N * 3^L). N is the number of cells in the board, and L is the length of the word. Each DFS call explores up to 3 directions (excluding the direction it came from), leading to O(3^L) exploration per start cell. Since DFS is initiated from each cell, total complexity is O(N * 3^L).

Problem

Given a 2D board of characters and a string word, return true if the word exists in the grid by sequentially adjacent cells (horizontally or vertically), without revisiting any cell.

1 ≤ board.length ≤ 200
1 ≤ board[i].length ≤ 200
1 ≤ word.length ≤ 10³
board and word consist only of uppercase and lowercase English letters.

Example

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

Output: true

Starting at board[0][0] = 'A', the algorithm explores neighbors to match 'B', then 'C', continuing to 'C', 'E', and 'D'. The critical moment is at board[0][2] = 'C', where the algorithm must choose the correct path to continue matching the word without revisiting cells. Backtracking ensures that if a path fails, the algorithm reverts state and tries alternative routes until the word is found or all options are exhausted.

Approach

Straightforward Solution

A brute-force approach tries every cell as a starting point and explores all possible paths recursively, checking if the word can be formed. Without pruning or state tracking, this leads to exponential time complexity and redundant exploration.

Core Observation

The problem requires searching for a path in a grid that matches a sequence of characters, with the constraint that each cell can be used only once per path. This naturally models a stateful exploration problem where the search space is a graph of grid cells connected by adjacency.

Path to Optimal

Preview

The key insight is to use Depth-First Search (DFS) combined with backtracking to explore paths. By marking cells as visited during exploration and unmarking them when backtracking, the algorithm avoids revisiting cells in the same path and prunes invalid paths early…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a DFS helper function that takes the current cell coordinates and the index of the character to match. The function returns true if the remaining substring can be matched starting from that cell…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(N * 3^L)

N is the number of cells in the board, and L is the length of the word. Each DFS call explores up to 3 directions (excluding the direction it came from), leading to O(3^L) exploration per start cell. Since DFS is initiated from each cell, total complexity is O(N * 3^L).

Space

O(L)

The recursion stack and the path set grow at most to the length of the word L, which is the maximum depth of the DFS recursion. The visited set uses O(L) auxiliary space as well.

Solution

Python

1class Solution:
  def exist(self, board: list[list[str]], word: str) -> bool:
      ROWS, COLS = len(board), len(board[0])
      path = set()
5
      def dfs(r, c, i):
          if i == len(word):
              return True
          if (r < 0 or c < 0 or
              r >= ROWS or c >= COLS or
              word[i] != board[r][c] or
              (r, c) in path):
              return False
          
          path.add((r, c))
          res = (dfs(r + 1, c, i + 1) or
                 dfs(r - 1, c, i + 1) or
                 dfs(r, c + 1, i + 1) or
                 dfs(r, c - 1, i + 1))
          path.remove((r, c))
          return res
22
      for r in range(ROWS):
          for c in range(COLS):
              if dfs(r, c, 0):
                  return True
      return False

Step-by-Step Solution

1

Set Up Board Dimensions and Visited Path Tracking

3ROWS, COLS = len(board), len(board[0])
4path = set()

Objective

To store the board's dimensions and initialize a set to track visited cells during DFS.

Key Insight

Knowing the board's size upfront allows efficient boundary checks during DFS. The visited set is critical to enforce the constraint that each cell can be used only once per path, preventing cycles and invalid matches. Using a set of coordinate tuples provides O(1) membership checks.

Interview Quick-Check

Core Logic

Storing board dimensions once avoids repeated calls to len() during recursion, improving efficiency.

State & Boundaries

The visited set tracks the current path's cells, ensuring no cell is revisited in the same search branch.

2

Perform DFS with Boundary, Match, and Visited Checks

To recursively explore adjacent cells matching the next character in the word, while enforcing boundaries and visited constraints.

3

Mark Current Cell, Explore Neighbors, and Backtrack

To mark the current cell as visited, recursively search all four adjacent directions for the next character, and unmark the cell to restore state.

4

Initiate DFS from Each Cell and Return Final Result

To iterate over every cell in the board as a potential starting point and return true if any DFS call finds the word.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 20 Critical

path.remove((r, c))

Remove the current cell from the visited set to backtrack.

Backtracking restores state so other paths can reuse this cell, enabling exhaustive search without violating constraints.

Line 7 Critical

if i == len(word):

Check if the entire word has been matched.

This base case terminates recursion successfully when all characters have been found in sequence.

Line 11 Critical

word[i] != board[r][c] or

Check if the current board cell does not match the current word character.

Mismatch pruning stops exploration along invalid paths early, improving efficiency.

Full line-by-line criticality + rationale for all 22 lines available on Pro.

Test Your Understanding

Why is it necessary to remove a cell from the visited path after exploring all its neighbors in DFS?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Word Search from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Word Search drill

or drill a free problem

1	`class Solution:`
2	`def exist(self, board: list[list[str]], word: str) -> bool:`
3	`ROWS, COLS = len(board), len(board[0])`
4	`path = set()`
5
6	`def dfs(r, c, i):`
7	`if i == len(word):`
8	`return True`
9	`if (r < 0 or c < 0 or`
10	`r >= ROWS or c >= COLS or`
11	`word[i] != board[r][c] or`
12	`(r, c) in path):`
13	`return False`
14
15	`path.add((r, c))`
16	`res = (dfs(r + 1, c, i + 1) or`
17	`dfs(r - 1, c, i + 1) or`
18	`dfs(r, c + 1, i + 1) or`
19	`dfs(r, c - 1, i + 1))`
20	`path.remove((r, c))`
21	`return res`
22
23	`for r in range(ROWS):`
24	`for c in range(COLS):`
25	`if dfs(r, c, 0):`
26	`return True`
27	`return False`