hardBacktrackingPure DSA~38 min
Keyword Grid Search
A word-puzzle feature lets users hunt for a keyword inside a letter grid. A match walks between horizontally or vertically adjacent cells, and no cell may be reused within a single match. Decide whether the keyword exists.
Problem
Given an m×n grid of characters and a word, return true if the word can be formed by a path of adjacent (up/down/left/right) cells, where each cell is used at most once.
Input
A grid of size m×n (1 ≤ m, n ≤ 6 for the hardest cases, up to 200 cells) and a string word (1 ≤ length ≤ 15).
Output
A boolean — true if the word can be traced on the grid.
Constraints
- Adjacency is four-directional
- A cell cannot be reused within one match
- Characters are uppercase ASCII letters
Examples
Example 1
Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output
true
Path A(0,0)→B(0,1)→C(0,2)→C(1,2)→E(2,2)→D(2,1) traces the word.
Example 2
Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output
false
Reaching the second B would require reusing the only B cell.