Skip to main content

21. Word Search

mediumAsked at SoFi

Determine if a word can be constructed in a 2D board by walking adjacent cells without reuse — SoFi uses this DFS/backtracking classic to test recursion-with-rollback intuition.

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 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","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED"
Output
true

Example 2

Input
board=[["A","B"]], word="BA"
Output
true

Approaches

1. Brute force string-matching

Try every cell as a start and recursively explore neighbors, but track visited via a Set of "i,j" strings.

Time
O(m*n*4^L)
Space
O(L + m*n)
function exist(board, word) {
  const visit = new Set();
  const dfs = (i, j, k) => {
    if (k === word.length) return true;
    const key = i+','+j;
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
        || visit.has(key) || board[i][j] !== word[k]) return false;
    visit.add(key);
    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);
    visit.delete(key);
    return found;
  };
  for (let i=0;i<board.length;i++)
    for (let j=0;j<board[0].length;j++)
      if (dfs(i,j,0)) return true;
  return false;
}

Tradeoff:

2. In-place DFS with sentinel

Mutate the board cell to a sentinel '#' while recursing, then restore on backtrack — avoids extra space.

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 || i >= m || j < 0 || j >= n || board[i][j] !== word[k]) return false;
    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] = word[k];
    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:

SoFi-specific tips

SoFi looks for backtracking with proper cleanup — fractional-share order-routing engines explore allocation paths and must restore state on rejection, so candidates who use sentinels cleanly get bonus signal.

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

Practice these live with InterviewChamp.AI →