Search on a grid

Before you start

• Graphs

  A grid is a graph whose neighbors are the four adjacent cells. Number of Islands walks one the same way.

  Open lesson

Why it matters

Word puzzles, maze rules, and board games often ask whether one path spells or reaches a target. The search must try alternatives, yet a cell used earlier in the same path cannot be used again, and failed attempts must not damage later attempts. The answer must enforce adjacency and single-use cells while leaving the board unchanged.

Return true if word can be formed from adjacent (4-dir) cells without reusing a cell.

Input

board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCCED"

Output

True

On the given 3 × 4 board, an unrestricted search for "ABCCED" can reuse cells, while copying a visited set at every branch wastes memory. Mark the A-B-C-C-E-D path in place, restore it on return, and stop at the first full match.

For "ABCCED", start at A in (0, 0), then follow B at (0, 1), C at (0, 2), C at (1, 2), E at (2, 2), and D at (2, 1). A wrong letter or an off-board coordinate returns False for that direction.

Before leaving each matched cell, replace it with "#"; deeper calls therefore cannot reuse it. When the call returns, restore its original letter, whether that branch failed or found the word. After the D match, i reaches 6 and returns True, ending the remaining search.