Skip to main content

23. Word Search

mediumAsked at Wix

Find a word by traversing a character grid without reusing cells — Wix tests this backtracking pattern as a stand-in for constraint-propagation problems like detecting valid UI element placements in a grid-based layout canvas.

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

Problem

Given an m x n grid of characters and a string word, return true if the word exists in the grid. The word must be constructed from sequentially adjacent cells (horizontally or vertically neighbouring). 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 only 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 = "ABCB"
Output
false

Explanation: B at position [0][1] cannot be reused

Approaches

1. Backtracking DFS

For each cell matching word[0], launch a DFS. Mark a cell visited by temporarily replacing it; unmark it on backtrack.

Time
O(m * n * 4^L) where L = word length
Space
O(L) recursion depth
function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[idx]) return false;

    const tmp = board[r][c];
    board[r][c] = '#'; // mark visited
    for (const [dr, dc] of dirs) {
      if (dfs(r + dr, c + dc, idx + 1)) {
        board[r][c] = tmp;
        return true;
      }
    }
    board[r][c] = tmp; // unmark
    return false;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

Tradeoff:

2. Backtracking DFS with frequency pruning

Before DFS, count letter frequencies in the board and in word. If the word needs more of any letter than the board has, return false immediately. Also reverse word if the last character is rarer, to cut branches faster.

Time
O(m * n * 4^L) worst case, significantly faster in practice
Space
O(L)
function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;

  // Frequency pruning
  const freq = {};
  for (const row of board)
    for (const ch of row)
      freq[ch] = (freq[ch] || 0) + 1;
  for (const ch of word) {
    freq[ch] = (freq[ch] || 0) - 1;
    if (freq[ch] < 0) return false;
  }

  // Reverse word if last char is rarer (fewer starts)
  const wArr = word.split('');
  if ((freq[wArr[0]] || 0) > (freq[wArr[wArr.length - 1]] || 0)) {
    wArr.reverse();
  }
  const w = wArr.join('');

  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

  function dfs(r, c, idx) {
    if (idx === w.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== w[idx]) return false;
    const tmp = board[r][c];
    board[r][c] = '#';
    for (const [dr, dc] of dirs) {
      if (dfs(r + dr, c + dc, idx + 1)) {
        board[r][c] = tmp;
        return true;
      }
    }
    board[r][c] = tmp;
    return false;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

Tradeoff:

Wix-specific tips

Wix values the backtracking instinct — the in-place mark-and-unmark pattern shows you understand how to manage shared mutable state without extra memory. Mention the frequency pruning optimisation and you'll stand out; it shows you think about pruning the search tree before the first recursive call, not just during it.

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

Practice these live with InterviewChamp.AI →