124. Word Search — Single Word
Spell the word by walking through orthogonally adjacent board cells, matching its characters in order. A coordinate may appear at most once in one candidate path.
Finding all letters somewhere on the board is not enough; the path must connect them in the correct order. Restore the board after any temporary search markings.
Example 1
Input
board=["ab","ca"], word="aba"
Output
true
Explanation: Coordinates (0,0)→(0,1)→(1,1) spell the word without reuse.
Example 2
Input
board=["ab","cd"], word="aba"
Output
false
Explanation: Returning from b to the original a would reuse a coordinate.
Example 3
Input
board=["ax","xb"], word="ab"
Output
false
Explanation: The matching letters are diagonal, which is not a legal edge.
Example 4
Input
board=[], word=""
Output
true
Explanation: The empty path is a witness even without a start cell.
Constraints
0 <= board.length <= 1050 <= total board cells <= 105- The board is rectangular. Compare UTF-16 code units exactly; no cell may be reused within one word path.
Hints
Hint 1
The same coordinate can be available in one branch and unavailable in another.
Hint 2
A frame needs its current cell, matched prefix index, and where to resume neighbor scanning.
Hint 3
Push only unused matching neighbors; pop and unmark exhausted frames, and unwind the successful path before returning.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
A complete witness is followed by explicit cleanup
["ab","ca"]
"aba"
true