Determine whether a target word can be formed by tracing adjacent cells in a 2D board without reusing a cell.
Problem
You are given a 2D grid of characters and a target string word.
Return true if word can be constructed by starting at any cell and moving through horizontally or vertically adjacent cells to match the characters in order. Each cell may be used at most once in a path.
A valid path must match every character of the word exactly.
Key idea
This is a path-search problem on a matrix with a "visit once" constraint, which typically requires backtracking.
Input Format
board: a 2D array of single lowercase charactersword: a non-empty string
Output Format
- Return
trueif the word exists in the board, otherwise returnfalse.
Constraints
- The path may start at any cell.
- Moves are allowed only up, down, left, or right.
- A cell cannot be reused in the same path.
- The board contains at least one cell.
Example 1
Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output
true
Explanation
One valid path is A -> B -> C -> C -> E -> D using adjacent cells without reusing any cell.
Example 2
Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output
false
Explanation
The word would require reusing a cell, which is not allowed.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.