86. Word Search

Medium · Backtracking

You are given a 2D grid of letters and a word. Your task is to determine whether the word can be found in the grid by moving through orthogonally adjacent cells (up, down, left, right) without reusing any cell.

Input: An array containing [board, word], where board is a 2D array of single-character strings and word is the target string to find.

Return: true if the word can be spelled by following a valid path through adjacent cells, or false otherwise.

Examples

Example 1
Input: [[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED"]
Output: true
Explanation: Path exists
Example 2
Input: [[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB"]
Output: false
Explanation: Cell reuse required

Constraints