Skip to main content

63. Word Search

mediumAsked at Snowflake

Given a 2D board, find whether a word can be constructed by adjacent cells without reusing a cell. Snowflake asks this to test DFS-with-backtrack on a grid — same shape as path-discovery during dependency-graph traversal of materialized views.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake new-grad onsite to set up MV-dependency follow-up.
  • LeetCode Discuss (2025-10)— Reported at Snowflake SDE-I screens.

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 = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output
true

Example 3

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

Approaches

1. DFS with visited set

From each cell, DFS in four directions; track visited via a Set of (r, c) keys.

Time
O(m * n * 4^L)
Space
O(L + m*n)
// outline only — works but allocates Set per call.

Tradeoff: Works but allocations slow it down.

2. DFS with in-place marking (optimal)

Temporarily set board[r][c] = '#' during recursion, restore on return. No extra visited 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 saved = 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] = saved;
    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: In-place marking uses the input grid as visited storage — O(1) extra per cell.

Snowflake-specific tips

Snowflake interviewers want the in-place marker trick (saved + restore). Bonus signal: connect to materialized-view dependency-graph traversal — when refreshing an MV that depends on others, the engine DFS-marks visited nodes to detect cycles and order refreshes.

Common mistakes

  • Forgetting to restore the cell after recursion — corrupts subsequent searches.
  • Marking before the bounds/char check — must do the check first so we don't mark an invalid cell.
  • Returning true too early before all four directions have been tried.

Follow-up questions

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

  • Word Search II (LC 212) — multiple words, use a Trie.
  • How does Snowflake order MV refreshes?
  • Cycle detection in a DAG.

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 in-place marking?

Avoids allocating a Set or visited grid per call. The saved/restore pattern keeps the board correct for sibling searches.

How does this connect to MV refresh?

Refreshing an MV that depends on others requires a topological order. The DFS marks visited nodes to detect cycles and emit a valid order. Word Search is the simpler version: DFS on a grid with backtracking.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →