Word Search

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).

Q: 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.

Medium DFS

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

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. This approach systematically explores all valid paths without repetition, ensuring correctness and efficiency.

Optimal Approach

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.

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.

Pattern Spotlight

DFS (Stateful Exploration with Backtracking)

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.

Solution

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

1import java.util.HashSet;
2import java.util.Set;
3
4public class Solution {
  public boolean exist(char[][] board, String word) {
      int ROWS = board.length;
      int COLS = board[0].length;
      Set<String> path = new HashSet<>();
9
      // DFS helper function
      // r, c: current cell coordinates
      // i: current index in word
      // returns true if word[i:] can be matched starting from board[r][c]
      class DFS {
          boolean dfs(int r, int c, int i) {
              if (i == word.length()) {
                  return true;
              }
              if (r < 0 || c < 0 || r >= ROWS || c >= COLS || word.charAt(i) != board[r][c] || path.contains(r + "," + c)) {
                  return false;
              }
22
              path.add(r + "," + c);
              boolean res = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
              path.remove(r + "," + c);
              return res;
          }
      }
29
      DFS helper = new DFS();
      for (int r = 0; r < ROWS; r++) {
          for (int c = 0; c < COLS; c++) {
              if (helper.dfs(r, c, 0)) {
                  return true;
              }
          }
      }
      return false;
  }
40}

1#include <vector>
2#include <string>
3#include <unordered_set>
4
5using namespace std;
6
7class Solution {
8public:
9    bool exist(vector<vector<char>>& board, string word) {
10        int ROWS = board.size();
11        int COLS = board[0].size();
12        unordered_set<string> path;
13
14        function<bool(int,int,int)> dfs = [&](int r, int c, int i) -> bool {
15            if (i == (int)word.size()) {
16                return true;
17            }
18            if (r < 0 || c < 0 || r >= ROWS || c >= COLS || word[i] != board[r][c] || path.count(to_string(r) + "," + to_string(c))) {
19                return false;
20            }
21
22            path.insert(to_string(r) + "," + to_string(c));
23            bool res = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
24            path.erase(to_string(r) + "," + to_string(c));
25            return res;
26        };
27
28        for (int r = 0; r < ROWS; r++) {
29            for (int c = 0; c < COLS; c++) {
30                if (dfs(r, c, 0)) {
31                    return true;
32                }
33            }
34        }
35        return false;
36    }
37};

1var exist = function(board, word) {
  const ROWS = board.length;
  const COLS = board[0].length;
  const path = new Set();
5
  function dfs(r, c, i) {
      if (i === word.length) {
          return true;
      }
      if (r < 0 || c < 0 || r >= ROWS || c >= COLS || word[i] !== board[r][c] || path.has(r + "," + c)) {
          return false;
      }
13
      path.add(r + "," + c);
      const res = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
      path.delete(r + "," + c);
      return res;
  }
19
  for (let r = 0; r < ROWS; r++) {
      for (let c = 0; c < COLS; c++) {
          if (dfs(r, c, 0)) {
              return true;
          }
      }
  }
  return false;
28};

Step-by-Step Solution

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.

Perform DFS with Boundary, Match, and Visited Checks

6def 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

Objective

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

Key Insight

The DFS function first checks if the entire word has been matched, returning true as a success base case. It then validates that the current cell is within bounds, matches the current character, and is not already in the path. These checks prune invalid paths early, preventing unnecessary recursion. This disciplined pruning is essential to keep the search tractable.

Interview Quick-Check

Core Logic

The base case `i == len(word)` confirms the entire word has been matched, terminating recursion successfully.

State & Boundaries

Boundary and visited checks prevent invalid or repeated cell usage, maintaining correctness.

Common Pitfalls & Bugs

Forgetting to check if a cell is already visited can cause infinite loops or incorrect matches.

Mark Current Cell, Explore Neighbors, and Backtrack

15path.add((r, c))
16res = (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))
20path.remove((r, c))
21return res

Objective

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

Key Insight

Marking the cell before recursion prevents revisiting it in the current path. Exploring all four directions ensures all possible paths are considered. The use of logical OR aggregates results, returning true if any path succeeds. Backtracking by removing the cell from the visited set restores the state for other search branches, enabling exhaustive exploration without interference.

Interview Quick-Check

Core Logic

Backtracking restores the visited state after exploring neighbors, allowing other paths to reuse the cell.

Common Pitfalls & Bugs

Failing to backtrack (remove from visited) leads to incorrect pruning of valid paths.

Complexity

Exploring four directions at each step leads to exponential branching, but pruning and visited checks keep it manageable.

Initiate DFS from Each Cell and Return Final Result

23for r in range(ROWS):
24    for c in range(COLS):
25        if dfs(r, c, 0):
26            return True
27return False

Objective

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

Key Insight

Since the word can start anywhere, the algorithm must attempt DFS from all cells. Early return upon success avoids unnecessary computation. If no path matches the word, the function returns false, indicating the word does not exist in the board.

Interview Quick-Check

Core Logic

Starting DFS from every cell ensures all possible word placements are considered.

State & Boundaries

Returning immediately upon a successful DFS call optimizes runtime by avoiding redundant searches.

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.

Line 12 Critical

(r, c) in path):

Check if the current cell has already been visited in this path.

Preventing revisits enforces the problem's constraint and avoids infinite recursion.

Line 15 Critical

path.add((r, c))

Add the current cell to the visited set.

Marking the cell as visited prevents revisiting it in the current path, maintaining correctness.

Line 26 Critical

return True

Return true immediately if DFS finds the word.

Early termination upon success avoids unnecessary further searches, optimizing runtime.

Line 4 Core

path = set()

Initialize a set to track visited cells in the current search path.

The visited set enforces the constraint that each cell can be used only once per path, preventing cycles and invalid matches.

Line 9 Core

if (r < 0 or c < 0 or

Check if the current cell is out of bounds or invalid.

Boundary checks prevent invalid memory access and ensure the search stays within the grid.

Line 13 Core

return False

Return false if any invalid condition is met.

This early return prunes invalid paths, preventing wasted computation.

Line 21 Core

return res

Return true if any recursive call found a valid path, else false.

Aggregating results with logical OR ensures the function returns success if any path matches the word.

Line 25 Core

if dfs(r, c, 0):

Invoke DFS from the current cell to search for the word.

Starting DFS from each cell ensures all possible placements of the word are explored.

Line 8 Core

return True

Return true when the word is fully matched.

Returning true here signals that a valid path has been found, propagating success up the recursion stack.

Line 10 Core

r >= ROWS or c >= COLS or

Check if the current cell is beyond the last row or column.

This complements the previous boundary checks, fully validating the cell's position.

Line 16 Core

res = (dfs(r + 1, c, i + 1) or

Recursively explore the cell below for the next character.

Exploring downward adjacency is part of exhaustive search for the word path.

Line 17 Core

dfs(r - 1, c, i + 1) or

Recursively explore the cell above for the next character.

Exploring upward adjacency ensures all vertical paths are considered.

Line 18 Core

dfs(r, c + 1, i + 1) or

Recursively explore the cell to the right for the next character.

Exploring rightward adjacency covers horizontal paths.

Line 19 Core

dfs(r, c - 1, i + 1))

Recursively explore the cell to the left for the next character.

Exploring leftward adjacency completes the four-directional search.

Line 27 Core

return False

Return false if no DFS call finds the word.

Indicates the word does not exist in the board after exhaustive search.

Line 23 Standard

for r in range(ROWS):

Iterate over each row in the board as a potential start.

Since the word can start anywhere, all cells must be considered as starting points.

Line 24 Standard

for c in range(COLS):

Iterate over each column in the board as a potential start.

Completes the iteration over all cells in the grid.

Line 6 Standard

def dfs(r, c, i):

Define the DFS helper function with current cell coordinates and word index.

Encapsulating the recursive search logic in a helper function allows clean state management and recursion control.

Line 3 Standard

ROWS, COLS = len(board), len(board[0])

Store the number of rows and columns in the board.

Caching the board dimensions enables efficient boundary checks during DFS without repeated calls to len(), improving performance.

Test Your Understanding

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

Removing the cell from the visited path (backtracking) restores the state so that other paths can reuse that cell, ensuring all possible paths are explored without violating the no-revisit constraint within a single path.

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`

1	`import java.util.HashSet;`
2	`import java.util.Set;`
3
4	`public class Solution {`
5	`public boolean exist(char[][] board, String word) {`
6	`int ROWS = board.length;`
7	`int COLS = board[0].length;`
8	`Set<String> path = new HashSet<>();`
9
10	`// DFS helper function`
11	`// r, c: current cell coordinates`
12	`// i: current index in word`
13	`// returns true if word[i:] can be matched starting from board[r][c]`
14	`class DFS {`
15	`boolean dfs(int r, int c, int i) {`
16	`if (i == word.length()) {`
17	`return true;`
18	`}`
19	`if (r < 0 \|\| c < 0 \|\| r >= ROWS \|\| c >= COLS \|\| word.charAt(i) != board[r][c] \|\| path.contains(r + "," + c)) {`
20	`return false;`
21	`}`
22
23	`path.add(r + "," + c);`
24	`boolean res = dfs(r + 1, c, i + 1) \|\| dfs(r - 1, c, i + 1) \|\| dfs(r, c + 1, i + 1) \|\| dfs(r, c - 1, i + 1);`
25	`path.remove(r + "," + c);`
26	`return res;`
27	`}`
28	`}`
29
30	`DFS helper = new DFS();`
31	`for (int r = 0; r < ROWS; r++) {`
32	`for (int c = 0; c < COLS; c++) {`
33	`if (helper.dfs(r, c, 0)) {`
34	`return true;`
35	`}`
36	`}`
37	`}`
38	`return false;`
39	`}`
40	`}`

1	`#include <vector>`
2	`#include <string>`
3	`#include <unordered_set>`
4
5	`using namespace std;`
6
7	`class Solution {`
8	`public:`
9	`bool exist(vector<vector<char>>& board, string word) {`
10	`int ROWS = board.size();`
11	`int COLS = board[0].size();`
12	`unordered_set<string> path;`
13
14	`function<bool(int,int,int)> dfs = [&](int r, int c, int i) -> bool {`
15	`if (i == (int)word.size()) {`
16	`return true;`
17	`}`
18	`if (r < 0 \|\| c < 0 \|\| r >= ROWS \|\| c >= COLS \|\| word[i] != board[r][c] \|\| path.count(to_string(r) + "," + to_string(c))) {`
19	`return false;`
20	`}`
21
22	`path.insert(to_string(r) + "," + to_string(c));`
23	`bool res = dfs(r + 1, c, i + 1) \|\| dfs(r - 1, c, i + 1) \|\| dfs(r, c + 1, i + 1) \|\| dfs(r, c - 1, i + 1);`
24	`path.erase(to_string(r) + "," + to_string(c));`
25	`return res;`
26	`};`
27
28	`for (int r = 0; r < ROWS; r++) {`
29	`for (int c = 0; c < COLS; c++) {`
30	`if (dfs(r, c, 0)) {`
31	`return true;`
32	`}`
33	`}`
34	`}`
35	`return false;`
36	`}`
37	`};`

1	`var exist = function(board, word) {`
2	`const ROWS = board.length;`
3	`const COLS = board[0].length;`
4	`const path = new Set();`
5
6	`function dfs(r, c, i) {`
7	`if (i === word.length) {`
8	`return true;`
9	`}`
10	`if (r < 0 \|\| c < 0 \|\| r >= ROWS \|\| c >= COLS \|\| word[i] !== board[r][c] \|\| path.has(r + "," + c)) {`
11	`return false;`
12	`}`
13
14	`path.add(r + "," + c);`
15	`const res = dfs(r + 1, c, i + 1) \|\| dfs(r - 1, c, i + 1) \|\| dfs(r, c + 1, i + 1) \|\| dfs(r, c - 1, i + 1);`
16	`path.delete(r + "," + c);`
17	`return res;`
18	`}`
19
20	`for (let r = 0; r < ROWS; r++) {`
21	`for (let c = 0; c < COLS; c++) {`
22	`if (dfs(r, c, 0)) {`
23	`return true;`
24	`}`
25	`}`
26	`}`
27	`return false;`
28	`};`

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`

Problem

Example

Approach

Solution

Step-by-Step Solution

Set Up Board Dimensions and Visited Path Tracking

Perform DFS with Boundary, Match, and Visited Checks

Mark Current Cell, Explore Neighbors, and Backtrack

Initiate DFS from Each Cell and Return Final Result

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.