Skip to main content

63. Word Search

mediumAsked at Ola

Determine if a word exists in a 2D board by visiting 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 the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontal/vertical neighbors). 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

Examples

Example 1

Input
board = [["A","B"],["C","D"]], word = "AB"
Output
true

Example 2

Input
board = [["A","B"],["C","D"]], word = "AC"
Output
true

Approaches

1. Brute path enumeration

Enumerate every connected path of length |word|.

Time
exp
Space
exp
// path enumeration without pruning; impractical even for tiny boards

Tradeoff:

2. DFS with visit marker

Start DFS from any matching cell; temporarily mark visited; revert on backtrack.

Time
O(m*n*4^L)
Space
O(L)
function exist(board, word) {
  const m = board.length, n = board[0].length;
  const 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:

Ola-specific tips

Ola uses this to verify careful backtracking restore; tie it to following a fixed token sequence across a connected zone grid.

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

Practice these live with InterviewChamp.AI →