Skip to main content

27. Word Search

mediumAsked at Dropbox

Determine whether a word exists by tracing adjacent cells in a 2D grid — Dropbox maps this to path-finding in a file-system graph where each directory is a cell and you must navigate without revisiting a node.

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

Problem

Given an m×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 (horizontally or vertically neighboring). 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 uppercase and lowercase 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. Backtracking DFS

For each cell that matches word[0], launch a DFS. At each step mark the current cell visited (e.g. overwrite with '#'), recurse in four directions, then restore. Return true immediately on a full match.

Time
O(m*n * 4^L) where L = word.length
Space
O(L) recursion stack
function exist(board, word) {
  const m = board.length;
  const n = board[0].length;
  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[idx]) return false;
    const tmp = board[r][c];
    board[r][c] = '#';
    const found =
      dfs(r + 1, c, idx + 1) ||
      dfs(r - 1, c, idx + 1) ||
      dfs(r, c + 1, idx + 1) ||
      dfs(r, c - 1, idx + 1);
    board[r][c] = tmp;
    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:

2. Backtracking with early-exit pruning

Before DFS, count character frequencies in board vs word. If the word needs more of any character than the board contains, return false immediately. Optionally reverse the word if the last character is rarer — reduces branching factor early.

Time
O(m*n * 4^L) with practical speedup from pruning
Space
O(L)
function exist(board, word) {
  const m = board.length;
  const n = board[0].length;
  const boardFreq = {};
  for (const row of board) for (const ch of row) boardFreq[ch] = (boardFreq[ch] || 0) + 1;
  const wordFreq = {};
  for (const ch of word) wordFreq[ch] = (wordFreq[ch] || 0) + 1;
  for (const [ch, cnt] of Object.entries(wordFreq)) {
    if ((boardFreq[ch] || 0) < cnt) return false;
  }
  if ((boardFreq[word[0]] || 0) > (boardFreq[word[word.length - 1]] || 0)) {
    word = word.split('').reverse().join('');
  }
  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[idx]) return false;
    const tmp = board[r][c];
    board[r][c] = '#';
    const found =
      dfs(r + 1, c, idx + 1) ||
      dfs(r - 1, c, idx + 1) ||
      dfs(r, c + 1, idx + 1) ||
      dfs(r, c - 1, idx + 1);
    board[r][c] = tmp;
    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:

Dropbox-specific tips

Dropbox occasionally frames this as path-tracing in a directory DAG: 'Can you reach folder Z from folder A without revisiting any node?' The key skill they're grading is clean backtracking — restore state before returning, don't use a separate visited set when in-place marking is possible, and explain the time complexity as branching-factor to the power of path length.

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

Practice these live with InterviewChamp.AI →