Word Search

You're given an m x n grid of letters called board and a target string word. Return true if word can be spelled out by walking through the grid, and false otherwise.

A path may start at any cell. From a cell you may step to a horizontally or vertically adjacent cell — up, down, left, or right, never diagonally. Each step must land on the next letter of word, and no cell may be used more than once within a single path.

Hints

· Stuck? Reveal one nudge at a time.

Where could a valid path possibly begin? Only on a cell that already matches the word's first letter.

As you walk the trail, how do you stop yourself from stepping on the same cell twice within one path?

Blank out a cell before you recurse into its neighbors and restore it right after — that's backtracking on a grid.

Common doubts

No — only to horizontally or vertically adjacent cells (up, down, left, right).

No. Each cell is used at most once per path. Different paths are free to reuse cells.

No. It just has to spell word — any leftover cells are ignored.

Interview follow-ups

· What an interviewer asks next.

Prune before searching: if word needs more of some letter than the board holds, return early; and search from the rarer endpoint by reversing word when its last letter is scarcer than its first.

Build a Trie of all the words and DFS the board a single time, walking the Trie in lockstep with the grid instead of restarting per word.

Fun facts

The mark-and-restore trick here is the exact same engine that solves mazes, Sudoku, and N-Queens — backtracking is one idea wearing many costumes.
Add a Trie and this problem becomes its harder sibling that searches for a whole dictionary of words in one board sweep.

Asked at

AmazonMicrosoftBloombergFacebookGoogle

Frequently Sometimes Occasionally

Example 1

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Trace A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(2,2) → D(2,1).

Example 2

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Trace S(1,3) → E(2,3) → E(2,2).

Example 3

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
The only path spelling ABC dead-ends; the second B is never reachable without reusing a cell.

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.

Word Search is the canonical first step into backtracking on a grid — searching for a path, undoing your choices, and pruning dead ends. Here's the arc from a plain scan to a pruned search.

Prerequisites

Before you start

· Concepts used directly in the solution.

Depth-first search. You explore one trail as far as it goes before trying another.

Backtracking. After exploring a choice you undo it, restoring the board for the next attempt.

Grid neighbors. Each cell connects to up to four others — up, down, left, right.

Understand the problem

Formally: starting from some cell, can you form word by moving through orthogonally adjacent cells, matching letter by letter, using each cell at most once along the path?

Worked example — word = SEE

  A B C E
  S F C S
  A D E E

  start (1,3)=S → (2,3)=E → (2,2)=E
  spells S-E-E  ✓  answer: true

Clarifying questions

Asking these before coding shows you're mapping the rules of movement, not guessing.

Questions to ask first

· Signals seniority before you write a line of code.

Movement rules

“Are diagonal steps allowed, or only up-down-left-right?”

Diagonals would add four more directions to every recursive call.

Cell reuse

“Can the same cell be used twice in one word?”

No reuse per path is the whole reason we mark and restore cells.

Constraints and scale

“How large can the board and word get?”

Tiny here (m, n <= 6), so plain backtracking passes; larger boards would need pruning.

The ideal opening — say it like this

Before I code, a couple of clarifications.

Are moves strictly horizontal and vertical, with no diagonals?

And within a single path, a cell can't be reused — correct?

Key observations

1Aha

A trail can only begin on the first letter

Every valid path's first cell equals word[0], so we only launch a search from those cells — a mismatch elsewhere dies instantly.

2Aha

Mark-and-restore forbids reuse cleanly

Before recursing into a cell's neighbors, overwrite it with a sentinel like #; restore it afterward. No separate visited-set to keep in sync.

  visit (0,0)=A → board[0][0]='#'
    ... explore neighbors ...
  done          → board[0][0]='A'   (restored)

3Aha

Fail fast, and start from the rarer end

The first letter mismatch kills a branch. For larger boards, if the last letter is rarer than the first, search the word reversed so fewer branches ever start.

Brute force vs optimal

	Brute force	Optimal
Time	O(m·n·4^L)	O(m·n·4^L) worst, pruned in practice
Space	O(L)	O(L)
Extra work	searches every start	skips impossible words, starts from rarer end

See the full code for each approach in the Approaches selector below.

Summary

Key takeaway

Word Search is grid backtracking: choose a cell, mark it, explore its neighbors, then un-mark it. Add a feasibility check and a rare-end start when the board grows.

for each cell (r,c):
    if dfs(r, c, 0): return true
return false

dfs(r, c, i):
    if out of bounds or board[r][c] != word[i]: return false
    if i == last index: return true
    save board[r][c]; board[r][c] = '#'
    found = dfs(up) or dfs(down) or dfs(left) or dfs(right)
    restore board[r][c]
    return found