Skip to main content

79. Word Search

mediumAsked at Cisco

Word Search at Cisco is a DFS-on-grid problem with backtracking. The interviewer is checking whether you mark cells as visited BEFORE the recursion and unmark AFTER — the classic 'place + try + unplace' backtracking template.

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

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-II onsite reports cite Word Search as a 30-45 minute DFS round.
  • Blind (2025-10)— Cisco interview thread lists Word Search as a recurring backtracking problem.

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

Explanation: Cannot reuse the same B.

Approaches

1. Brute-force with visited set

For each cell, DFS using a Set to track visited cells. Return true the moment any starting cell finds the word.

Time
O(m * n * 4^L)
Space
O(m * n + L)
function existBrute(board, word) {
  const m = board.length, n = board[0].length;
  const visited = new Set();
  function dfs(r, c, k) {
    if (k === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    const key = r * n + c;
    if (visited.has(key) || board[r][c] !== word[k]) return false;
    visited.add(key);
    const found = dfs(r+1, c, k+1) || dfs(r-1, c, k+1) || dfs(r, c+1, k+1) || dfs(r, c-1, k+1);
    visited.delete(key);
    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: Correct. Allocates O(m*n) for the visited set. Cisco accepts this; the optimal mutates the board to save the set.

2. DFS with in-place marking (optimal)

Instead of a Set, temporarily overwrite the cell with a sentinel (e.g., '#') during recursion. Restore on the way back up.

Time
O(m * n * 4^L)
Space
O(L) recursion stack
function exist(board, word) {
  const m = board.length, n = board[0].length;
  function dfs(r, c, k) {
    if (k === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[k]) return false;
    const saved = board[r][c];
    board[r][c] = '#';
    const found = dfs(r+1, c, k+1) || dfs(r-1, c, k+1) || dfs(r, c+1, k+1) || dfs(r, c-1, k+1);
    board[r][c] = saved;
    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: Cleaner than the Set version and uses O(L) space (just the recursion depth). The 'mark then unmark' pattern is the canonical backtracking template. Cisco interviewers expect this.

Cisco-specific tips

Cisco interviewers grade this on the backtracking template — say it out loud: 'I mark the cell, recurse into the four neighbors, then unmark on the way back up. The unmark is what makes it backtracking instead of plain DFS.' That sentence is the entire signal. State the pruning: 'I return false immediately if the character doesn't match' so the recursion tree gets cut early. Mention in-place vs. visited-set as the space optimization.

Common mistakes

  • Forgetting to UNMARK the cell on the way back up — the same cell stays unavailable for OTHER starting positions and you'll miss valid paths.
  • Returning true after one neighbor matches WITHOUT short-circuiting — JS's `||` short-circuits naturally, but if you use any() or all() patterns elsewhere, beware.
  • Forgetting the bounds check at the TOP of dfs — the recursive call passes potentially out-of-bounds (r, c).

Follow-up questions

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

  • Word Search II (LC 212) — multiple words; use a Trie of all words to prune entire subtrees.
  • What if the word can wrap around the grid edges? (Torus boundary — modulo arithmetic on indices.)
  • Return ALL paths that spell the word, not just true/false.
  • Largest word that exists in the grid — try words in decreasing length order.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

In-place marking or visited Set — which is preferred?

In-place is the canonical answer because it uses O(L) space instead of O(m*n). The downside is you're mutating the input; if the interviewer says 'do not modify the board', fall back to the Set. Always ASK first.

Why is this called backtracking, not plain DFS?

Plain DFS marks visited cells once and never unmarks. Backtracking unmarks ON THE WAY BACK UP so the cell can be reused by other paths. The key property: the search tree is a DAG of DECISIONS, and backtracking undoes the decision when it doesn't lead to a solution.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →