Skip to main content

79. Word Search

mediumAsked at Netflix

Given an m x n grid of characters and a word, check whether the word exists in the grid by walking 4-directionally without reusing cells. Netflix asks this on the DFS round — they want clean backtracking with in-place visited-marking and pruning.

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

Source citations

Public interview reports confirming this problem appears in Netflix loops.

  • Glassdoor (2026-Q1)— Netflix L4 onsite reports cite Word Search as a 40-minute backtracking question.
  • Blind (2025-10)— Netflix SWE writeups list this as the DFS/backtracking question on the algorithms loop.

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 = "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 starting cell whose char matches word[0], DFS in four directions, tracking visited cells in a set keyed by (r, c).

Time
O(m * n * 4^L) where L = word.length
Space
O(L) for recursion + O(L) for the visited set
function existSet(board, word) {
  const m = board.length, n = board[0].length;
  function dfs(r, c, i, seen) {
    if (i === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    const key = r * n + c;
    if (seen.has(key) || board[r][c] !== word[i]) return false;
    seen.add(key);
    const ok = dfs(r + 1, c, i + 1, seen) || dfs(r - 1, c, i + 1, seen) || dfs(r, c + 1, i + 1, seen) || dfs(r, c - 1, i + 1, seen);
    seen.delete(key);
    return ok;
  }
  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: Correct and clear, but the Set allocations add overhead. Mention it as the readable version before the in-place trick.

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

Same DFS but mark visited by overwriting board[r][c] with a sentinel like '#'. Restore it on backtrack. Saves the Set allocation.

Time
O(m * n * 4^L)
Space
O(L) recursion only
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 ok = 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 ok;
  }
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) {
    if (dfs(r, c, 0)) return true;
  }
  return false;
}

Tradeoff: O(1) extra per recursive frame — no per-cell set entries. Mutating input is acceptable here because we restore it on backtrack; mention this aloud so the interviewer knows you considered it.

Netflix-specific tips

Netflix interviewers want two specific things: (1) The in-place marking trick — saves memory and is the version on the rubric. State explicitly that you'll restore on backtrack. (2) Pruning: a starting cell whose char doesn't equal word[0] should be skipped immediately. They'll also probe: 'What if the word is much longer than the grid?' (Answer: prune if word.length > m * n.)

Common mistakes

  • Forgetting to restore board[r][c] on backtrack — leaves the board mutated for the next start cell, breaking subsequent searches.
  • Using `board[r][c] = '#'` after the bounds check instead of inside the recursion — wastes work on invalid cells.
  • Not pruning starting cells where board[r][c] !== word[0] before launching DFS.

Follow-up questions

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

  • Word Search II (LC 212) — multiple words at once; use a Trie.
  • What if the grid had 8 directions including diagonals?
  • Could you parallelize the search across multiple cores? (Yes — independent starting cells.)

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 is mutating the board acceptable here?

Because we restore the original character on every backtrack — the board returns to its original state once DFS unwinds. State this explicitly to the interviewer: it's a borrow-and-return, not a permanent mutation.

What's the worst-case time complexity?

O(m * n * 4^L) where L is word.length. The 4^L term is the branching factor at each DFS step (modulo bounds and visited). In practice early prune on board[r][c] !== word[i] keeps it manageable.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →