Skip to main content

29. Word Search

mediumAsked at Postman

Check whether a word can be formed in a 2D grid by traversing adjacent cells.

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

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; the same cell may not be reused.

Constraints

  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • Grid and word contain only 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","D"]], word = "ABDC"
Output
false

Approaches

1. DFS with visited Set

DFS from every cell, tracking visited coordinates in a Set of `${i},${j}` strings.

Time
O(m * n * 4^L)
Space
O(L)
// pass set of visited keys down through recursion

Tradeoff:

2. DFS with in-place marking

DFS from every cell; temporarily overwrite visited cells with a sentinel, restore on backtrack. Avoids per-recursion-allocation.

Time
O(m * n * 4^L)
Space
O(L)
function exist(board, word) {
  const r = board.length, c = board[0].length;
  const dfs = (i, j, k) => {
    if (k === word.length) return true;
    if (i < 0 || j < 0 || i >= r || j >= c || 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 < r; i++) for (let j = 0; j < c; j++) if (dfs(i, j, 0)) return true;
  return false;
}

Tradeoff:

Postman-specific tips

Postman uses backtracking with restore-on-unwind for collection path-search — interviewers will ask whether you mutate the input, so be explicit about restoring.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →