Skip to main content

59. Word Search

mediumAsked at Workday

Determine if a word exists in a grid of letters using adjacent cells. Workday uses this for DFS-with-backtracking + visited-marking — same shape as searching for a specific approval-chain path through a workflow graph.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025-Q4)— Workday SDE2 onsite — DFS canonical.

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
Same board, word = "SEE"
Output
true

Example 3

Input
Same board, word = "ABCB"
Output
false

Approaches

1. BFS

BFS from each starting cell.

Time
O(m*n * 4^L) where L = len(word)
Space
O(m*n)
// BFS works but managing 'visited' per path is awkward

Tradeoff: Visited needs to be path-local, which BFS makes awkward — use DFS.

2. DFS with in-place visited mark

DFS from each cell. Mark visited by temporarily overwriting the cell, 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 saved = 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] = saved;
    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: Single visited-mark via temporary cell overwrite. Saves O(m*n) for an explicit visited matrix.

Workday-specific tips

Workday grades on backtracking discipline: restore board[i][j] after each DFS, even on failure. The in-place '#' marker is the canonical trick — articulate why it saves O(m*n) space.

Common mistakes

  • Forgetting to restore the cell on backtrack — corrupts the board for future starting cells.
  • Checking k == word.length AFTER advancing instead of as base case.
  • Using an explicit visited matrix — works but uses more space.

Follow-up questions

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

  • Word Search II (LC 212) — multiple words, use trie.
  • Number of Islands (LC 200).
  • Longest Increasing Path in a Matrix (LC 329).

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 restore on backtrack?

Other DFS starting cells might want to visit this cell along a different path. Without restoration, the board permanently marks cells as visited from a failed attempt.

Why DFS over BFS?

DFS naturally manages a path-local visited set via call-stack restoration. BFS would need to track visited-per-path explicitly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →