The core approach: Word Search is solved with DFS backtracking in O(m×n×4^L) time and O(L) space, where L is word length. From each cell, recursively try all four directions matching the next character. Mark cells as visited in place to prevent reuse on the same path, then unmark them on backtrack to allow other paths.

You’re in a coding interview. The interviewer says: “Given a 2D board and a word, determine if the word exists in the grid by traversing adjacent cells without reusing a cell.” This is DFS with backtracking on a grid. The key: mark cells as visited during the search and unmark them after — that’s the backtracking step.

---

Already know how to solve Word Search? Try a Word Search mock interview on Intervu →

The Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word must be constructed from sequentially adjacent cells (horizontally or vertically). The same cell may not be used more than once.

Example

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true

---

What Interviewers Are Actually Testing

Skill	What Interviewers Observe
DFS + backtracking	Do you use the mark/unmark visited pattern?
Early termination	Do you check character match before recursing?
All starting cells	Do you try DFS from every matching first character?
In-place marking	Do you mark cells in place vs. separate set?

---

Step 1: The Key Insight

DFS + backtracking: mark a cell as visited before exploring neighbors, then unmark after (whether you succeed or fail). This lets other paths reuse cells from dead-end branches. Try every cell as a potential starting point.

---

Python Implementation

def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def dfs(r: int, c: int, index: int) -> bool:
        if index == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[index]:
            return False

        temp = board[r][c]
        board[r][c] = '#'  # mark visited

        for dr, dc in directions:
            if dfs(r + dr, c + dc, index + 1):
                board[r][c] = temp
                return True

        board[r][c] = temp  # unmark — backtrack
        return False

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

---

Time & Space Complexity

Aspect	Complexity
Time	O(m × n × 4^L) — L is word length
Space	O(L) — recursion stack

---

Common Interview Mistakes

1. Not unmarking visited cells. Other paths can’t reuse cells from dead-end branches. Always restore.
2. Wrong early-exit order. Check bounds and character match before accessing board[r][c].
3. Not trying all starting cells. Must iterate every cell as a potential start.

---

What a Strong Candidate Sounds Like

“For each cell, I run DFS matching character by character. I mark cells visited in-place with ’#’, restore after recursion — that’s the backtracking. I return true as soon as any path completes the word. Time is O(m·n·4^L), space O(L).”

---

Related Problems to Practice

• Number of Islands — Grid DFS without backtracking.
• Flood Fill — Grid DFS with implicit visited.
• Subsets — Pure backtracking, same build/recurse/undo.

---

Frequently Asked Questions

What drives the recursive letter matching inside Word Search?

Depth-First Search coupled with aggressive Backtracking drives the matrix exploration perfectly. You plunge forward searching adjacent cells character-by-character along an assumed correct path. If a branch inevitably hits dead-end non-matching letters, you immediately backtrack backwards to explore alternative valid routes cleanly.

How do you prevent identical grid blocks from artificially looping?

As the algorithm traverses forward matching characters, you dynamically modify the active coordinate value locally into a distinct visited symbol (like #). Upon backtracking from a failed deeper plunge, you simply restore the original legitimate character backwards, naturally opening that block again for entirely separate pathway scans.

Practice This in a Mock Interview

Start a mock interview for Word Search on Intervu.

---

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code