79. Word Search
You are given an m × n grid of letters board and a string word. Decide whether word can be traced through the grid: start on any cell, and at every step move to an edge-adjacent cell — up, down, left, or right, never diagonally. A cell may be used at most once within a single trace.
Return true if some path through the grid spells word, and false otherwise. Matching is case-sensitive.
Example 1:
Input: board = ["ABCE", "SFCS", "ADEE"], word = "ABCCED"
Output: true
Explanation: Start at the top-left 'A', go right through 'B' and 'C', then down through the second 'C' and 'E', then left to 'D' — six distinct cells spelling ABCCED.
Example 2:
Input: board = ["ABCE", "SFCS", "ADEE"], word = "ABCB"
Output: false
Explanation: After A → B → C the only adjacent 'B' is the one already used, and reusing a cell is not allowed.
Constraints:
- 1 ≤ m, n ≤ 6
- 1 ≤ word.length ≤ 15
- board and word consist of uppercase and lowercase English letters
- Matching is case-sensitive: 'A' and 'a' are different letters
Hints:
Any cell can be the start, so try them all. From a cell matching word[i], the trace must continue into a neighbor matching word[i + 1] — that sentence is already a recursion.
Enforce use-once with backtracking: overwrite the cell with a sentinel like '#' before recursing into its neighbors, and restore the letter afterwards. No visited-set copies needed.
Prune before searching: count the board's letters once — if the word demands more copies of some letter than the board holds, answer false immediately. Starting the search from the rarer end of the word also slashes the number of live branches.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: board = ["ABCE", "SFCS", "ADEE"], word = "ABCCED"
Expected output: true