Skip to main content

22. Word Search

mediumAsked at MercadoLibre

Decide whether a word can be traced through neighboring cells of a 2D grid.

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 (horizontally or vertically) and the same cell may not be used more than once.

Constraints

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

Approaches

1. DFS with extra visited matrix

Try DFS from every start cell, tracking visited cells in a separate boolean matrix.

Time
O(m*n*4^L)
Space
O(m*n + L)
const seen = Array.from({length:m}, () => new Array(n).fill(false));
function dfs(r, c, k) {
  if (k === word.length) return true;
  if (r<0||c<0||r>=m||c>=n||seen[r][c]||board[r][c]!==word[k]) return false;
  seen[r][c] = true;
  const ok = dfs(r+1,c,k+1) || dfs(r-1,c,k+1) || dfs(r,c+1,k+1) || dfs(r,c-1,k+1);
  seen[r][c] = false;
  return ok;
}
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. DFS with in-place marking

Mark visited cells by mutating the board itself, then restore on backtrack — saves the visited matrix.

Time
O(m*n*4^L)
Space
O(L)
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 tmp = board[r][c]; board[r][c] = '#';
    const ok = 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] = tmp;
    return ok;
  }
  for (let r=0;r<m;r++) for (let c=0;c<n;c++) if (dfs(r,c,0)) return true;
  return false;
}

Tradeoff:

MercadoLibre-specific tips

MercadoLibre search teams ask this to gauge backtracking discipline — useful for catalog-text matching where product attributes must appear in adjacent fields without falling back into duplicate cells.

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

Practice these live with InterviewChamp.AI →