Skip to main content

19. Word Search

mediumAsked at Autodesk

Determine if a word exists in a 2D board, walking through orthogonally 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 sequentially adjacent cells (horizontal or vertical neighbors), and the same cell may not be used more than once.

Constraints

  • 1 <= m, n <= 6
  • 1 <= word.length <= 15

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="ACDB"
Output
true

Approaches

1. Enumerate all paths

Generate every path of length word.length and check equality.

Time
O(mn * 4^L)
Space
O(L)
// generates all length-L paths from every start cell - blows up quickly.

Tradeoff:

2. Backtracking DFS

From each starting cell that matches word[0], DFS and temporarily mark visited cells; restore on backtrack so the cell is reusable for other starts.

Time
O(mn * 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 || j < 0 || i >= m || j >= n || 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 < m; i++) for (let j = 0; j < n; j++)
    if (dfs(i, j, 0)) return true;
  return false;
}

Tradeoff:

Autodesk-specific tips

Backtracking grid traversal is exactly the shape Autodesk uses for CAD pattern-matching searches on raster blueprints.

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

Practice these live with InterviewChamp.AI →