Skip to main content

20. Word Search

mediumAsked at Quora

Find a word hidden in a 2-D character grid — Quora applies this backtracking-DFS pattern to their entity-extraction engine when scanning structured text fields for keyword sequences.

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

Constraints

  • 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 = "SEE"
Output
true

Approaches

1. Backtracking DFS

For each cell matching word[0], DFS all four directions while tracking visited cells via in-place marking. Undo the mark 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(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[idx]) return false;
    const tmp = board[r][c];
    board[r][c] = '#';
    const found = dfs(r+1, c, idx+1) || dfs(r-1, c, idx+1) ||
                  dfs(r, c+1, idx+1) || dfs(r, c-1, idx+1);
    board[r][c] = tmp;
    return found;
  }
  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. Backtracking DFS with early frequency pruning

Before DFS, check whether the board has enough of each required character. If word needs more 'A' than the board contains, return false immediately.

Time
O(m * n * 4^L)
Space
O(L)
function exist(board, word) {
  const m = board.length, n = board[0].length;
  const boardFreq = {}, wordFreq = {};
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      boardFreq[board[r][c]] = (boardFreq[board[r][c]] || 0) + 1;
  for (const ch of word) wordFreq[ch] = (wordFreq[ch] || 0) + 1;
  for (const ch of Object.keys(wordFreq))
    if ((boardFreq[ch] || 0) < wordFreq[ch]) return false;
  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[idx]) return false;
    const tmp = board[r][c];
    board[r][c] = '#';
    const found = dfs(r+1,c,idx+1)||dfs(r-1,c,idx+1)||dfs(r,c+1,idx+1)||dfs(r,c-1,idx+1);
    board[r][c] = tmp;
    return found;
  }
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (dfs(r, c, 0)) return true;
  return false;
}

Tradeoff:

Quora-specific tips

Quora's interviewers often ask this after graph questions to probe your pruning instinct. The frequency-precheck is a small constant-time win that signals you think about worst-case inputs before writing the recursive skeleton.

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

Practice these live with InterviewChamp.AI →