Skip to main content
DSA is fun
Lesson mode

Word Search

Word Search tries each matching start cell and backtracks through unused horizontal or vertical neighbors.

backtracking
matrix
dfs
Pattern connection

This lesson reinforces Backtracking & Subsets.

Open Backtracking & Subsets

Problem in simple words

Given a grid of letters and a word, decide whether the word can be traced through a chain of adjacent cells without reusing any cell.

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED".
Output: true (A→B→C→C→E→D traced through adjacent cells).

Core idea

A path can reuse the board shape but not the same cell within one attempt.

How the algorithm thinks

  1. 1

    Try starting the word at each board cell

    VISIT

    A matching first letter anywhere on the board is a candidate starting point worth exploring further.

    Watch: The cell currently being checked as a start.

  2. 2

    Mark the cell and branch to its neighbors

    CALL

    Once a cell matches the needed letter, it's marked as used and every unused neighboring direction is tried for the next letter.

    Watch: The cell being marked, and the four directions being tried.

  3. 3

    Unmark and back out when no neighbor works

    BACKTRACK

    If none of the neighbors continue the word, this cell must be freed up again so a different path can still use it.

    Watch: The cell being unmarked.

  4. 4

    Return whether any path completed the word

    RETURN

    If any branch of the search matched every character of the word, the word exists on the board.

    Watch: The final true or false answer.

Step-by-step logic

  • -For each cell on the board, try starting the word search there.
  • -At each step, check whether the current index has reached the word's length (success), whether the cell is off the board or already used or doesn't match the needed letter (failure).
  • -If the cell matches, mark it as used and recursively try all four neighboring directions for the next letter.
  • -Whether or not a direction succeeds, unmark the current cell once its neighbors have all been tried, so the cell is available again for a different path.

Complexity

Time O(mn*4^L)·Space O(L)

each start can branch through up to four neighbors for L word characters.

Implementation

This is the JavaScript implementation that generates the simulator timeline.

function exist(input) {
  for each start cell, dfs with a visited set;
  backtrack when a branch fails;
}

Common mistakes

Leaving a cell marked as used after backtracking, which would incorrectly block other valid paths from using it.
Checking bounds or letter matches before the completion check, which can cause incorrect behavior right at the final character.
Including diagonal neighbors in the search, which would find paths that aren't actually valid under the problem's rules.
Predict

Pause before the next step and name the state change you expect.

Trace

Watch the active pointers, discarded range, and output state and match it to the highlighted code line.

Explain

Say the rule that never breaks (the invariant) out loud: what remains true before and after this step?

  • -Step 1: (0,0)='A' matches word[0]='A' -- mark it used.
  • -Step 2: down (1,0)='S' fails to match 'B'; up is off the board; right (0,1)='B' matches word[1] -- mark it used.
  • -Step 3: down (1,1)='F' fails; up is off the board; right (0,2)='C' matches word[2] -- mark it used. Down from there, (1,2)='C' matches word[3] -- mark it used. Down again, (2,2)='E' matches word[4] -- mark it used.
  • -Step 4: from (2,2), down is off the board, up is already used, right (2,3)='E' fails to match 'D', left (2,1)='D' matches word[5] -- the word is complete.

Recursion Foundations
beginner
  • - What should this function promise to do?
  • - Where does the recursion stop?
  • - Which smaller problem can you trust?
  • - How does current work connect with the smaller answer?
Open foundation
Backtracking Foundations
beginner
  • - List the choices at each step.
  • - Reject invalid choices early.
  • - Explore one choice completely.
  • - Undo the choice before trying the next branch.
Open foundation
Graph Traversal Foundations
intermediate
  • - Choose queue for levels or stack/recursion for depth.
  • - Mark visited at the right time.
  • - Track frontier, traversal order, and parent/dependency state.
Open foundation
Two Pointers Foundations
beginner
  • - Decide what each pointer represents.
  • - Move the pointer that can safely eliminate work.
  • - Keep the invariant true after every move.
Open foundation

Next step

Build the reasoning before opening the simulator

Turn the mental model into a short decision checklist, then compare it with the execution timeline.