Skip to main content

59. Word Search

mediumAsked at Vercel

Given a 2D board of letters and a word, return whether the word exists by adjacent-cell traversal. Vercel asks this for the DFS-with-visited-marker pattern — same shape as their route-prefix matching across the layout tree.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; DFS backtracking expected.
  • Blind (2026-Q1)— Listed in Vercel screen pool.

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 = "SEE"
Output
true

Example 3

Input
Same board, word = "ABCB"
Output
false

Approaches

1. DFS with a Set of visited coords

Track visited cells in a Set; recurse 4 directions.

Time
O(m*n*4^L)
Space
O(L) for path + O(m*n) for Set
function exist(board, word) {
  const m = board.length, n = board[0].length;
  function dfs(r, c, i, visited) {
    if (i === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || visited.has(r * n + c) || board[r][c] !== word[i]) return false;
    visited.add(r * n + c);
    const found = dfs(r+1,c,i+1,visited) || dfs(r-1,c,i+1,visited) || dfs(r,c+1,i+1,visited) || dfs(r,c-1,i+1,visited);
    visited.delete(r * n + c);
    return found;
  }
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) if (dfs(r, c, 0, new Set())) return true;
  return false;
}

Tradeoff: Set allocations slow it down. The in-place mark approach is preferred.

2. DFS with in-place character marking (optimal)

Temporarily set board[r][c] = '#' before recursion; restore after. Avoids the Set.

Time
O(m*n*4^L)
Space
O(L) recursion
function exist(board, word) {
  const m = board.length, n = board[0].length;
  function dfs(r, c, i) {
    if (i === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[i]) return false;
    const tmp = board[r][c];
    board[r][c] = '#';
    const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
    board[r][c] = tmp;
    return found;
  }
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) if (dfs(r, c, 0)) return true;
  return false;
}

Tradeoff: No visited Set; mutates the board temporarily. The character '#' isn't a valid letter, so it short-circuits the equality check naturally.

Vercel-specific tips

Vercel grades the in-place marking trick — saves allocations and is the canonical answer. Bonus signal: noting that you must restore the cell after recursion (this is the 'backtracking' part) and that the early-exit `board[r][c] !== word[i]` check is essential for pruning.

Common mistakes

  • Forgetting to restore the cell — corrupts the board for later starting positions.
  • Checking `board[r][c] !== word[i]` AFTER the recursion — wastes work; check first.
  • Allocating a new visited Set per recursion call instead of mutating one — wasteful.

Follow-up questions

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

  • Word Search II (LC 212, hard) — many words; use a Trie.
  • Diagonal moves allowed.
  • Largest connected island of a letter.

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 mutate the board?

It's a poor man's visited set with zero allocation. The temporary '#' character can't match any letter in the word, so the equality check naturally rejects it on revisit.

When is the Trie variant needed?

When searching for many words simultaneously (LC 212). A Trie lets you prune entire branches when no word continues with the current letter prefix.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →