Skip to main content

30. Word Search

mediumAsked at Lyft

Search for a word in a 2D character grid — Lyft applies the same DFS-with-backtracking to trace contiguous route segments on a map grid, checking if a sequence of location codes spells a valid service corridor.

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

Approaches

1. DFS with backtracking (in-place mark)

For each cell matching word[0], start DFS. At each step, mark the cell visited (temporarily with '#'), recurse on 4 neighbors for the next character, then unmark (backtrack). Return true if all characters matched.

Time
O(m * n * 4^L) where L = word.length
Space
O(L) recursion stack
function exist(board, word) {
  const m = board.length, n = 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 >= m || c < 0 || c >= n) 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; // backtrack
    return false;
  }

  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. DFS with visited set (no mutation)

Same DFS, but track visited cells in a Set of 'r,c' strings instead of mutating the board. Cleaner for interview readability; slightly higher space constant.

Time
O(m * n * 4^L)
Space
O(m * n + L)
function exist(board, word) {
  const m = board.length, n = board[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  const visited = new Set();

  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    if (board[r][c] !== word[idx]) return false;
    const key = `${r},${c}`;
    if (visited.has(key)) return false;
    visited.add(key);
    for (const [dr, dc] of dirs) {
      if (dfs(r + dr, c + dc, idx + 1)) { visited.delete(key); return true; }
    }
    visited.delete(key);
    return false;
  }

  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (dfs(r, c, 0)) return true;
  return false;
}

Tradeoff:

Lyft-specific tips

Lyft uses word search to test clean backtracking discipline. The most common mistake is forgetting to unmark the visited cell on the failure path — always say 'I restore state before returning false' when walking the interviewer through your code. If asked for an optimization, mention early-exit frequency pruning: count letter frequencies in the board and prune if the board doesn't have enough of each character in word before starting the DFS.

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

Practice these live with InterviewChamp.AI →