21. Word Search

Q: Why not use BFS here?

BFS finds shortest paths, not all paths. Since we need to track the exact sequence of cells (no reuse), DFS + backtracking is the natural fit — we need to undo state when a branch fails.

Q: What is the time complexity and why is it exponential?

At each step in the DFS, we have up to 3 unused neighbors (the 4th is where we came from). For a word of length L, that's at most 3^L paths per starting cell, times m*n starting cells — effectively O(m*n * 4^L) in the worst case.

mediumAsked at Adobe

Determine if a word exists in an m×n character grid where letters must be adjacent horizontally or vertically. Adobe uses this as a signature 2D DFS/backtracking problem — the grid-search pattern is directly applicable to font glyph shape recognition, texture atlas lookups, and region-growing algorithms in image segmentation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Adobe loops.

Glassdoor (2025-12)— Adobe SDE-II onsite consistently features word search or similar 2D DFS/backtracking problems.
LeetCode Discuss (2026-02)— Backtracking on 2D grids is a staple Adobe category tied to image processing themes.

Problem

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.

Constraints

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

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 = "ABCB"

Output

false

Explanation: Cannot reuse cell (0,1).

Approaches

1. DFS with visited set

For each cell matching the first character, DFS with a Set tracking visited cells.

Time: O(m*n*4^L) where L is word length
Space: O(m*n + L)

function exist(board, word) {
  const m = board.length, n = board[0].length;
  const visited = new Set();
  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    if (visited.has(`${r},${c}`)) return false;
    if (board[r][c] !== word[idx]) return false;
    visited.add(`${r},${c}`);
    const found = dfs(r+1,c,idx+1)||dfs(r-1,c,idx+1)||dfs(r,c+1,idx+1)||dfs(r,c-1,idx+1);
    visited.delete(`${r},${c}`);
    return found;
  }
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      if (dfs(i, j, 0)) return true;
  return false;
}

Tradeoff: Correct but the Set has overhead; in-place marking is preferred at Adobe.

2. Backtracking with in-place marking

Mark visited cells by temporarily replacing board[r][c] with a sentinel character (e.g., '#'), recurse in four directions, then restore. This avoids the overhead of a visited Set and makes the backtracking state visible directly in the grid.

Time: O(m*n*4^L)
Space: O(L) for recursion stack

function exist(board, word) {
  const m = board.length, n = board[0].length;
  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    if (board[r][c] !== word[idx]) return false;
    const temp = board[r][c];
    board[r][c] = '#';
    const found =
      dfs(r+1, c, idx+1) ||
      dfs(r-1, c, idx+1) ||
      dfs(r, c+1, idx+1) ||
      dfs(r, c-1, idx+1);
    board[r][c] = temp;
    return found;
  }
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      if (dfs(i, j, 0)) return true;
  return false;
}

Tradeoff: O(L) space for the call stack versus O(m*n) for a Set. The in-place marking and restoration is the canonical backtracking pattern Adobe interviewers look for.

Adobe-specific tips

Adobe interviewers grade this problem on correct backtracking discipline — explicitly restoring the cell after recursion. Failing to restore is a red flag. Also mention the early pruning optimization: before DFS, check that the frequency of each character in 'word' does not exceed its frequency in the board — this prunes hopeless searches early.

Common mistakes

Forgetting to restore board[r][c] after backtracking — this corrupts the board for other DFS paths.
Checking bounds after accessing board[r][c] — always bounds-check before indexing.
Not starting DFS from every cell — only looping from (0,0) misses starting positions.

Follow-up questions

An interviewer at Adobe may pivot to one of these next:

Word Search II (LC 212): find all words from a dictionary that exist in the board (use Trie + DFS).
How would you optimize if the word length is much larger than the board size?
What if you could move diagonally as well?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why not use BFS here?

BFS finds shortest paths, not all paths. Since we need to track the exact sequence of cells (no reuse), DFS + backtracking is the natural fit — we need to undo state when a branch fails.

What is the time complexity and why is it exponential?

At each step in the DFS, we have up to 3 unused neighbors (the 4th is where we came from). For a word of length L, that's at most 3^L paths per starting cell, times m*n starting cells — effectively O(m*n * 4^L) in the worst case.

Practice these live with InterviewChamp.AI

Drill Word Search and other Adobe interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →