Skip to main content

79. Word Search

mediumAsked at Atlassian

Word Search is an Atlassian DFS-backtracking problem. Given a grid of characters and a target word, return true if the word can be constructed from adjacent (horizontal/vertical) letters with no cell reused. Atlassian uses it to check whether you can write backtracking that cleans up after itself.

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

Source citations

Public interview reports confirming this problem appears in Atlassian loops.

  • Glassdoor (2026-Q1)— Atlassian SWE-II / Senior onsite reports cite Word Search as a recurring backtracking problem.
  • Blind (2025-10)— Atlassian interview threads list Word Search as the warm-up before Word Search II (trie + DFS).

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

Explanation: Cannot reuse B.

Approaches

1. Mark-in-place DFS backtracking (canonical)

From each cell matching word[0], DFS in four directions. Temporarily overwrite the cell with a sentinel '#' to mark visited; restore on unwind. Return true at full match.

Time
O(m * n * 4^L) where L = word length
Space
O(L) recursion
function exist(board, word) {
  const m = board.length;
  const n = board[0].length;
  const dfs = (r, c, i) => {
    if (i === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[i]) return false;
    const original = board[r][c];
    board[r][c] = '#';
    const found =
      dfs(r + 1, c, i + 1) ||
      dfs(r - 1, c, i + 1) ||
      dfs(r, c + 1, i + 1) ||
      dfs(r, c - 1, i + 1);
    board[r][c] = original;
    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: The Atlassian-canonical answer. Mark-in-place saves the O(m*n) visited-set memory; the catch is RESTORING the cell on unwind. Mention this aloud — half the bugs on this problem are forgetting the restore.

2. Separate visited set (no input mutation)

Same DFS but track visited cells in a Set keyed on r * n + c.

Time
O(m * n * 4^L)
Space
O(L + m*n)
function existSet(board, word) {
  const m = board.length;
  const n = board[0].length;
  const visited = new Set();
  const key = (r, c) => r * n + c;
  const dfs = (r, c, i) => {
    if (i === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    const k = key(r, c);
    if (visited.has(k) || board[r][c] !== word[i]) return false;
    visited.add(k);
    const found =
      dfs(r + 1, c, i + 1) ||
      dfs(r - 1, c, i + 1) ||
      dfs(r, c + 1, i + 1) ||
      dfs(r, c - 1, i + 1);
    visited.delete(k);
    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: Doesn't mutate the input — sometimes Atlassian's grading criteria explicitly forbids input mutation. Mention this version as the 'cleaner contract' alternative. Slightly more memory, slightly slower due to Set ops vs array writes.

Atlassian-specific tips

Atlassian explicitly grades 'restores state after backtrack'. Whichever version you ship, narrate the restore: 'mark, recurse, restore on unwind'. The micro-optimization Atlassian Senior interviewers like is the pruning 'if first letter doesn't even appear in the grid, return false early' — useful when the dictionary follow-up (Word Search II) arrives. Be ready to extend to trie-based DFS for that variant.

Common mistakes

  • Forgetting to restore board[r][c] = original after the recurse — subsequent searches in the outer loop break.
  • Using `||` short-circuit but with a `let found = false` instead — works, but the chained `||` version reads cleaner.
  • Skipping the i === word.length base case at the TOP of dfs — if you put it after the bounds check, the recursion incorrectly returns false at exact-match boundary.

Follow-up questions

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

  • Word Search II (LeetCode 212) — multiple words to search; trie of words + DFS over the grid; prune trie as you find matches.
  • What if word can wrap (toroidal grid)? Modulo r and c in the dfs.
  • What if cells can be reused? Drop the visited set; the algorithm becomes simpler but the answer space explodes.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Mark-in-place or visited set at Atlassian?

Either is accepted. Mark-in-place is more idiomatic and what most interviewers expect; visited set is the safer answer if the interviewer explicitly forbids input mutation. State both options aloud and pick one with a 5-second justification.

Why 4^L worst case?

At each step you have up to 4 unvisited neighbors and recurse to length L. The visited check prunes most branches in practice (grid is only 6x6 max), but the worst case for analysis is unconstrained 4-way branching.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →