Skip to main content

61. Word Search

mediumAsked at Salesforce

Determine if a word can be found in a 2D grid via adjacent cells (no revisits). Salesforce uses this to test DFS with backtracking and visited state.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses DFS-with-backtracking in their search-feature path queries.
  • Blind (2025-09)— Common Salesforce backend onsite question.

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
  • board and word consists of only 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","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output
true

Example 3

Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output
false

Approaches

1. Generate all paths and check

Enumerate all paths of length word.length; check against word.

Time
O(4^(m*n))
Space
O(huge)
// Not feasible.

Tradeoff: Explodes.

2. DFS with in-place visited marking

For each starting cell, DFS in 4 directions. Mark visited by mutating board[i][j] = '#'; restore on backtrack.

Time
O(m*n*4^L) where L = word.length
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 || i >= m || j < 0 || 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: In-place marking avoids a separate visited matrix. Restore-on-backtrack is essential.

Salesforce-specific tips

Salesforce uses DFS-with-backtracking heavily in their search-feature path queries. They grade on the restore-on-backtrack — forgetting it gives wrong answers on inputs where the path visits the same letter at different positions. Bonus signal: discuss the 'mark and restore' pattern as a general way to track in-place visited state.

Common mistakes

  • Using a separate visited matrix when board mutation is acceptable — wastes space.
  • Forgetting to restore board[i][j] — corrupts future searches.
  • Returning true unconditionally after one dfs succeeds — works in JS via short-circuit ||.

Follow-up questions

An interviewer at Salesforce may pivot to one of these next:

  • Word Search II (LC 212) — multiple words, use Trie.
  • Number of Islands (LC 200) — similar grid DFS.
  • Longest Increasing Path in a Matrix (LC 329).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why mutate the board instead of a visited array?

Saves O(m*n) memory. The mutation must be restored on backtrack so the function is idempotent.

Why include the start cell character check inside dfs?

Makes the function easier to call uniformly — every recursive call validates its position. The check inside subsumes the entry-point check.

Practice these live with InterviewChamp.AI

Drill Word Search and other Salesforce interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →