Word Search

Hard

DFS from every cell, undoing as you leave

Problem

Given a grid of letters and a word, return whether the word can be formed by adjacent cells (no cell reused).

In simple words

DFS from each cell, matching letters step by step and marking visited cells so you don't reuse them.

The idea

Start a depth-first search at each cell that matches the first letter and walk to neighbours matching the next one. Mark a cell as used before recursing and unmark it afterwards, so a cell is blocked only along the current path and remains available to other branches.

The trick

Mark the cell in place (overwrite with a sentinel) and restore it on the way out — no extra visited grid needed.
Return as soon as any branch succeeds; there is no need to explore the rest.
Failing fast on a letter mismatch is what keeps the search from exploding.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(m*n*4^L)spaceO(L)

1for each cell:2  dfs(r,c,i): if board[r][c]!=word[i]: return false3    mark visited; try 4 neighbours for i+1; unmark4  if dfs found: return true

Input

array: [0]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = "ABCCED"
Output:: true
Explanation:: The word snakes through neighbours.

Example 2

Input:: word = "SEE"
Output:: true
Explanation:: SEE is traceable.

Example 3

Input:: word = "ABCB"
Output:: false
Explanation:: Can't reuse a cell → false.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.