Word Search
Part of Practice: Duplicates & Grids
Given a 2D grid of letters and a target word, decide whether the word can be spelled by walking through the grid: start at any cell, and at each step move to a cell that shares an edge (up, down, left, or right — no diagonals). Each cell may be used at most once per path.
The grid is at most 6 × 6 and the word at most 15 letters, so an exponential search is acceptable — the challenge is doing the path search cleanly and undoing state correctly.
Examples
- Input:
- board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
- Output:
- true
Start at the top-left A, walk right along B, C, then down to the second-row C, down to E, left to D.
- Input:
- board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
- Output:
- true
Start at the S at the right end of row 2, move down to E, then left to the middle E of row 3.
- Input:
- board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
- Output:
- false
Spelling ABCB would need to revisit the already-used B — forbidden, so no valid path exists.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.