Skip to main content

61. Word Search

mediumAsked at Reddit

Check if a word exists in a 2D character grid (adjacent cells, no reuse). Reddit uses this to test DFS with backtracking on grids — the same shape used in their image-grid content-moderation when scanning for embedded text patterns.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, DFS warm-up.

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 consists 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 = same, word = "ABCB"
Output
false

Approaches

1. DFS with visited matrix

From each cell, DFS to neighbors; track a visited matrix.

Time
O(m*n*4^L)
Space
O(m*n)
function exist(board, word) {
  const m = board.length, n = board[0].length;
  const visited = Array.from({length: m}, () => new Array(n).fill(false));
  function dfs(i, j, k) {
    if (k === word.length) return true;
    if (i<0||i>=m||j<0||j>=n||visited[i][j]||board[i][j]!==word[k]) return false;
    visited[i][j] = true;
    const ok = dfs(i+1,j,k+1)||dfs(i-1,j,k+1)||dfs(i,j+1,k+1)||dfs(i,j-1,k+1);
    visited[i][j] = false;
    return ok;
  }
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) if (dfs(i,j,0)) return true;
  return false;
}

Tradeoff: Standard. visited matrix doubles memory.

2. DFS with in-place marker (optimal)

Temporarily overwrite board[i][j] with '#' during recursion; restore on return.

Time
O(m*n*4^L)
Space
O(L) recursion
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 tmp = board[i][j];
    board[i][j] = '#';
    const ok = 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] = tmp;
    return ok;
  }
  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) recursion stack; no visited matrix.

Reddit-specific tips

Reddit interviewers want backtracking with state restoration. Bonus signal: mention that for many words you'd use a Trie (LC 212 — Word Search II) to dedupe shared prefixes.

Common mistakes

  • Forgetting to restore board[i][j] after recursion.
  • Stopping at k === word.length - 1 (off by one).
  • Not checking bounds before accessing board[i][j].

Follow-up questions

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

  • Word Search II (LC 212) — multiple words via Trie.
  • Number of islands (LC 200) — same DFS template.
  • Surrounded regions (LC 130).

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 use board[i][j] = '#' instead of a visited set?

Same effect, no extra memory. Restore the original char on the way back up.

When would Trie be necessary?

When you have many candidate words sharing prefixes — Trie dedupes the prefix work. See LC 212.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →