Skip to main content

26. Word Search

mediumAsked at Tripadvisor

Find whether a word exists in a 2D character grid via adjacent cells — Tripadvisor's content team uses backtracking grid-search logic to detect destination or attraction name patterns embedded in structured review matrices.

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 neighboring). 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 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 = "ABCB"
Output
false

Approaches

1. Backtracking DFS (standard)

For each cell matching word[0], DFS to adjacent unvisited cells matching successive characters. Backtrack (restore the cell) on failure.

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, 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] = '#'; // mark visited
    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; // restore
    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 with frequency pruning

Before DFS, check that the board contains at least the required character frequencies. If not, immediately return false. Also reverse word if the last character is rarer — reduces search space significantly.

Time
O(m*n * 4^L) worst-case, much faster in practice
Space
O(L)
function exist(board, word) {
  const m = board.length, n = board[0].length;
  // Frequency pruning
  const freq = {};
  for (const row of board) for (const c of row) freq[c] = (freq[c] || 0) + 1;
  for (const c of word) { if (!freq[c]) return false; freq[c]--; }
  // Prefer searching from the rarer end
  const w = freq[word[0]] > freq[word[word.length-1]] ? word.split('').reverse().join('') : word;
  function dfs(r, c, idx) {
    if (idx === w.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== w[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:

Tripadvisor-specific tips

Tripadvisor interviewers appreciate seeing the backtracking-with-restoration pattern clearly — in-place mutation plus restore is cleaner than maintaining a separate visited set. The frequency-pruning optimization is a differentiator: it shows you think about cutting search early, which matters when the board represents a large content matrix. Walk through the time complexity O(m*n * 4^L) step by step — interviewers probe this formula directly.

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

Practice these live with InterviewChamp.AI →