Skip to main content

19. Word Search

mediumAsked at Freshworks

DFS-search a 2D grid for a word — Freshworks frames it as detecting a specific automation-rule signature path across a tag adjacency grid.

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

Problem

Given an m x n grid of characters and a word, return true if the word can be constructed from letters of sequentially adjacent cells. Each cell may be used at most once.

Constraints

  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consist of 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 = 'ABCB'
Output
false

Approaches

1. Brute force (visited Set)

DFS from every cell, tracking a visited Set keyed by 'r,c'. Works but allocates a Set per call.

Time
O(m*n*4^L)
Space
O(L + visited)
// recurse with a fresh `visited = new Set()` per starting cell
// add/remove 'r,c' keys; check `visited.has` per step

Tradeoff:

2. DFS with in-place marking

DFS from each cell. Match word[k]? Temporarily set board[r][c] = '#'. Recurse on 4 neighbors. Restore on backtrack.

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, k) {
    if (k === word.length) return true;
    if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] !== word[k]) return false;
    const saved = board[r][c]; board[r][c] = '#';
    const found = dfs(r+1,c,k+1) || dfs(r-1,c,k+1) || dfs(r,c+1,k+1) || dfs(r,c-1,k+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:

Freshworks-specific tips

Freshworks watches for the restore-on-backtrack step — candidates often forget it and accidentally permit cells from a failed branch in a later branch.

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

Practice these live with InterviewChamp.AI →