Skip to main content

60. Word Search

mediumAsked at Plaid

Determine if a word exists in a 2D grid by traversing adjacent cells. Plaid asks this as a DFS-on-grid baseline before harder graph-traversal problems on account-link graphs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II OA.
  • LeetCode Discuss (2026)— Plaid DFS-on-grid baseline.

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

Examples

Example 1

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

Example 2

Input
Same board, word = "ABCB"
Output
false

Approaches

1. BFS with visited set

BFS from every starting cell; track visited per path.

Time
O(m*n*4^L)
Space
O(L)
// BFS is awkward here because we need to track visited per-path, not globally.
// Don't ship.

Tradeoff: BFS doesn't fit cleanly because path-state is per-branch, not global.

2. DFS with in-place visited marker

From each cell, DFS in 4 directions. Mark visited cells with a sentinel; restore on backtrack.

Time
O(m*n*4^L)
Space
O(L)
function exist(board, word) {
  const m = board.length, n = board[0].length;
  function dfs(i, j, k) {
    if (k === word.length) return true;
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== word[k]) return false;
    const save = board[i][j];
    board[i][j] = '#';
    const found = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) || dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1);
    board[i][j] = save;
    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: In-place visited marker avoids allocating a separate set per call. The sentinel '#' must be a value not in the alphabet.

Plaid-specific tips

Plaid grades this on the in-place visited trick — saves a Set allocation per DFS call. Bonus signal: discuss the optimization of trying starting cells whose char matches word[0] first. Connect to account-link graph traversal where you DFS from a known account to verify a chain of OAuth handoffs.

Common mistakes

  • Forgetting to restore the cell on backtrack — pollutes the grid for subsequent starting positions.
  • Using a Set instead of in-place — works but allocates per call.
  • Off-by-one when checking k === word.length (some put the check after the comparison).

Follow-up questions

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

  • Word Search II (LC 212) — multiple words, use a Trie.
  • Path with maximum sum on a grid (LC 64).
  • Find all paths from source to target in a graph.

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 mark in-place and not use a Set?

Cheaper in both time and space. The sentinel approach is the standard for grid DFS when the grid's alphabet is bounded.

Why DFS and not BFS?

BFS would need per-path visited state, which doesn't fit cleanly. DFS naturally backtracks visited markers.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →