Skip to main content

19. Word Search

mediumAsked at Chegg

Search for a word in a 2D character grid using DFS with backtracking — tests backtracking fundamentals Chegg applies to plagiarism detection across document matrices.

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

Problem

Given an m x n board of characters and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically adjacent). The same 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

Approaches

1. DFS from every cell

Try DFS from each cell; no pruning — revisits redundant start positions.

Time
O(m*n*4^L)
Space
O(L)
function exist(board, word) {
  for (let i = 0; i < board.length; i++)
    for (let j = 0; j < board[0].length; j++)
      if (dfs(board, word, i, j, 0)) return true;
  return false;
}

Tradeoff:

2. DFS with in-place visited marking

Temporarily overwrite visited cells with '#' to avoid allocating a separate visited matrix; restore on backtrack for correctness.

Time
O(m*n*4^L)
Space
O(L) call stack
function exist(board, word) {
  const rows = board.length, cols = board[0].length;
  function dfs(i, j, idx) {
    if (idx === word.length) return true;
    if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] !== word[idx]) return false;
    const tmp = board[i][j];
    board[i][j] = '#';
    const found = dfs(i+1,j,idx+1) || dfs(i-1,j,idx+1) || dfs(i,j+1,idx+1) || dfs(i,j-1,idx+1);
    board[i][j] = tmp;
    return found;
  }
  for (let i = 0; i < rows; i++)
    for (let j = 0; j < cols; j++)
      if (dfs(i, j, 0)) return true;
  return false;
}

Tradeoff:

Chegg-specific tips

Chegg tests backtracking rigorously — always restore the cell value after recursion and mention how prefix frequency pruning (check board has enough of each letter before DFS) can cut runtime.

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 Chegg interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →