Word Search

Given an m x n board of letters and a word, return true if the word exists in the grid by sequentially adjacent cells (up/down/left/right). A cell may be used at most once.

Function signature

func Exist(board [][]byte, word string) bool

Inputs / outputs

• board: grid of letters.
• word: target word.
• Return: true if the word can be formed.

Example

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

Constraints

• 1 <= m, n <= 6
• 1 <= len(word) <= 15

Core idea (near-solution)

Use DFS backtracking from each cell that matches the first letter. Mark cells as visited during a path, then unmark when backtracking.

Invariant: the current path matches the first k letters of the word without reusing cells.

Algorithm (step-by-step)

1. For each cell, start DFS if it matches word[0].
2. In DFS, if index == len(word), return true.
3. Try four directions if next cell matches the next character and is unvisited.
4. Backtrack if no path works.

Correctness sketch

• Invariant: the current path matches the first k letters of the word without reusing cells.
• Each recursive step extends a valid partial solution.
• Backtracking explores all possible choices without duplication.
• Thus every valid solution is found and recorded.

Trace (hand walkthrough)

Example input:
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCCED"
Output: true

Walk:
- path for "ABCCED": A(0,0)->B(0,1)->C(0,2)->C(1,2)->E(2,2)->D(2,1)
- all moves are adjacent and no cell reused -> true

Pitfalls to avoid

• Not unmarking a cell on backtrack.
• Reusing a cell in the same path.

Complexity

• Time: O(m*n*4^L) in worst case.
• Extra space: O(L) recursion depth.

Implementation notes (Go)

• Mark a cell as visited by temporarily changing its value.
• Restore the cell after recursion to allow other paths.