MediumArrayStringBacktrackingDepth-First SearchMatrixUpdated Sep 2026

79. Word Search

Asked at Atlassian, Netflix, Oracle, Walmart and 1 more

Difficulty

Medium

Time

O(m * n * 4^L)

Space

O(L)

Pattern

Array

Companies

5

Problem

You are given a 2D grid of characters called board and a target word. Decide whether the word can be spelled out inside the grid.

To spell the word, you pick one cell for each letter, in order. Each next cell must touch the previous one horizontally or vertically (up, down, left, right — no diagonals). The same cell may not be used twice in one spelling.

Return true if at least one such path exists, otherwise return false.

Spell the word by walking to neighbors

board0123012ABCESFCSADEEThe green path spells A-B-C-C-E-D, moving onlyup/down/left/right.
Each letter must sit in a cell next to the previous one, and no cell can be visited twice.

Constraints

  • ●m == board.length
  • ●n == board[i].length
  • ●1 <= m, n <= 6
  • ●1 <= word.length <= 15
  • ●board and word contain only lowercase and uppercase English letters

Examples

Example 1
Inputboard = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Outputtrue
WhyStart at A (row 0, col 0), go right to B, right to C, down to the second C, down to E, then left to D. Every step moves to a neighbor and no cell is reused.
Example 2
Inputboard = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Outputtrue
WhyStart at S (row 1, col 3), go down to E, then left to E. Three cells, all adjacent, all different.
Example 3
Inputboard = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Outputfalse
WhyA → B → C works, but the only B next to that C is the B we already used. Reusing a cell is not allowed, so no valid path exists.

Asked At

5 companies
CompanyDifficulty
AtlassianMediumView all Atlassian questions →
NetflixMediumView all Netflix questions →
OracleMediumView all Oracle questions →
WalmartMediumView all Walmart questions →
BloombergMediumView all Bloomberg questions →

How to Think About It

1

Brute force: for every cell in the grid, start a DFS from that cell and try to match the entire word. That's O(m * n * 4^L) where L is the word length. Each cell has 4 directions, and you explore up to L levels deep.

2

Key insight: use backtracking. Start DFS from each cell that matches the first character. At each step, mark the current cell as visited (e.g., set to '#'), explore all 4 directions for the next character, then unmark when backtracking.

3

Why mark cells as visited: without marking, you might revisit the same cell in the same path, creating infinite loops. Setting the cell to a special character ('#') prevents revisiting. Unmarking when backtracking allows other paths to use this cell.

4

Pruning: if the current character doesn't match, stop immediately. You can also pre-check if the word's character counts exceed what's available in the grid, but that's an optimization, not required.

5

Edge cases: empty grid returns false. Empty word returns true. Word longer than grid size returns false. Word uses a character not in the grid returns false. Grid with one cell.

Optimal Approach

Step 1: For each cell (i, j) in the grid:

  • If grid[i][j] matches word[0], start DFS from (i, j) with index 0
    Step 2: DFS function at (i, j, index):
  • If index == len(word), return true (all characters matched)
  • If (i, j) is out of bounds or grid[i][j] != word[index], return false
  • Save grid[i][j], mark it as visited (set to a placeholder char)
  • Recurse in all 4 directions with index + 1
  • Unmark grid[i][j] (backtrack)
  • Return true if any direction returned true

Walkthrough for grid [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED":

  • Start DFS at (0,0)="A", index=0. Match. Mark visited.
  • (0,1)="B", index=1. Match. Mark visited.
  • (0,2)="C", index=2. Match. Mark visited.
  • (0,3)="E", index=3. Need "C", got "E". Fail. Backtrack.
  • (1,2)="C", index=3. Match. Mark visited.
  • (2,2)="E", index=4. Need "E", got "E". Match. Mark visited.
  • (2,1)="D", index=5. Need "D", got "D". Match. Index 6 == len(word). Return true.

Time: O(m * n * 4^L) worst case, but pruning makes it much faster in practice. Space: O(L) for the recursion stack (L = word length).

DFS with backtracking

step 10123012#BCESFCSADEEMatch 'A' at (0,0) and mark it '#' so this path cannotcome back.step 20123012###ESFCSADEEA → B → C all match. Going right to E fails, so we trydown instead.step 30123012###ESF#SAD#EDown to the second C, then down to E. Next we need D,which sits to the left.dfs(r, c, i): board[r][c] == word[i]mark '#', try 4 neighbors with i+1unmark on the way back
Mark a cell as used while you are standing on it, then unmark it when you leave so other paths can use it.
ComplexityTime O(m * n * 4^L)Space O(L)We try a DFS from every cell, and each step branches into up to 4 directions for L letters; the recursion stack holds at most L frames.

What Trips People Up in Real Interviews

1

Using a visited matrix instead of marking cells in-place. A separate visited matrix uses O(m*n) extra space. Marking cells with a placeholder character (like '#') and unmarking on backtrack is the standard in-place approach.

2

Forgetting to unmark (backtrack) after exploring a cell. If you don't restore the original character, other DFS paths from different starting cells can't use this cell, giving false negatives.

3

Trying to use BFS instead of DFS. BFS doesn't work well here because you need to track the exact path taken (which cells are in the current path). DFS naturally handles this with the call stack.

4

Not pruning early when the current character doesn't match. Without pruning, you explore all 4 directions even when the current cell doesn't match the needed character, wasting time.

5

Checking all 4 directions without short-circuit evaluation. Use if (dfs(...)) return true for each direction so you stop as soon as one path succeeds. Checking all directions unconditionally adds unnecessary work.

Solution Code

O(m * n * 4^L) time
def exist(board, word):
    if not board or not board[0]:
        return False
    rows, cols = len(board), len(board[0])

    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[idx]:
            return False
        temp = board[r][c]
        board[r][c] = '#'
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            if dfs(r+dr, c+dc, idx+1):
                return True
        board[r][c] = temp
        return False

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

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Word Search problem?

Given an m x n grid of characters and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically). Each cell can only be used once per search. This is a classic `backtracking` / `DFS` problem on a grid.

How do you solve Word Search?

The optimal approach runs in O(m * n * 4^L) time and O(L) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Word Search?

Word Search is asked at Atlassian, Netflix, Oracle, Walmart, Bloomberg. It is a medium difficulty problem.

What are common mistakes on Word Search?
  • Using a `visited` matrix instead of marking cells in-place. A separate `visited` matrix uses `O(m*n)` extra space. Marking cells with a placeholder character (like '#') and unmarking on backtrack is the standard in-place approach.
  • Forgetting to unmark (backtrack) after exploring a cell. If you don't restore the original character, other DFS paths from different starting cells can't use this cell, giving false negatives.
  • Trying to use `BFS` instead of `DFS`. BFS doesn't work well here because you need to track the exact path taken (which cells are in the current path). DFS naturally handles this with the call stack.
  • Not pruning early when the current character doesn't match. Without pruning, you explore all 4 directions even when the current cell doesn't match the needed character, wasting time.
  • Checking all 4 directions without short-circuit evaluation. Use `if (dfs(...)) return true` for each direction so you stop as soon as one path succeeds. Checking all directions unconditionally adds unnecessary work.