Skip to main content

22. Word Search

mediumAsked at Ramp

Determine if a word exists in a grid following adjacent cell moves.

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 letters of sequentially adjacent cells, where adjacent cells are 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

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 = "ABCB"
Output
false

Approaches

1. Brute-force DFS with copy-on-mark

DFS from every starting cell using a fresh visited set per branch.

Time
O(m*n*4^L)
Space
O(m*n)
function exist(board, word) {
  const m = board.length, n = board[0].length;
  function dfs(i, j, k, seen) {
    if (k === word.length) return true;
    if (i < 0 || j < 0 || i >= m || j >= n || seen.has(`${i},${j}`) || board[i][j] !== word[k]) return false;
    const next = new Set(seen); next.add(`${i},${j}`);
    return dfs(i+1,j,k+1,next) || dfs(i-1,j,k+1,next) || dfs(i,j+1,k+1,next) || dfs(i,j-1,k+1,next);
  }
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) if (dfs(i, j, 0, new Set())) return true;
  return false;
}

Tradeoff:

2. DFS with in-place sentinel marker

Temporarily overwrite the visited cell with a non-letter sentinel and restore on backtrack — avoids per-branch allocation.

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

Tradeoff:

Ramp-specific tips

Ramp grades the in-place sentinel trick highly because their corporate card rules engine evaluates condition trees under tight memory budgets — allocating a fresh visited set per branch is the anti-pattern they want you to avoid.

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

Practice these live with InterviewChamp.AI →