Word Search

Problem

You are given an m x n grid of letters board and a string word. Decide whether word can be traced in the grid by starting at any cell and moving to an orthogonally adjacent cell for each successive letter. Each cell may be used at most once within a single trace.

• The board has at most 10 rows and 10 columns.
• The word has at most 20 letters.
• board and word contain only letters.

Examples

• board = [["M","N","O","Q"],["T","R","O","T"],["M","P","Q","Q"]], word = "MNOOQP" → true. Start at (0,0), go right twice, down, down, left.
• Same board, word = "TQQ" → true. Start at (1,3), then (2,3), then (2,2).
• Same board, word = "MNON" → false. The only N adjacent to the final O is the one already used.

Hints

1. From any cell that matches word[0], what do you need to check next, and where?
2. A path cannot revisit a cell. How do you record "in use" while exploring, and what must you do when the exploration fails?
3. DFS from each matching start cell, matching one letter per step; temporarily mark the current cell (e.g. write '#') and restore it on the way back so other branches can use it.