You are given an m x n grid of characters board and a string word. Return true if word exists in the board.

The word can be formed by starting from any cell and moving to sequentially adjacent cells. Adjacent cells are only up, down, left, and right.

The same cell cannot be used more than once in the same word path.

Example 1:

Input: board = 
[["T", "R", "E", "A"],["X", "R", "U", "S"],["C", "E", "D", "E"]], 
word = "TREASURE"
Output: true

Explanation:
One valid path is: T → R → E → A → S → U → R → E
Using board positions: (0,0)→(0,1)→(0,2)→(0,3)→(1,3)→(1,2)→(1,1)→(2,1)

Example 2:

Input: board = 
[["F", "U", "N"],["A", "B", "N"],["C", "D", "K"]], word = "FUNNY"
Output: false

Explanation:
The first four characters can be formed: F → U → N → N
Using positions: (0,0) → (0,1) → (0,2) → (1,2)
The next required character is "Y", and there is no "Y" anywhere in the board.

Example 3:

Input: board = 
[["I", "H", "A"],["X", "T", "T"],["A", "T", "E"]], word = "IHATETAX"
Output: true

Explanation:
One valid path is: I → H → A → T → E → T → A → X
Using positions: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1)→(2,0)→(1,0)

Constraints

m == board.length

n == board[i].length

1 <= m <= 6

1 <= n <= 6

1 <= word.length <= min(15, m × n)

board is a rectangular grid

board[i][j] and word[k] are uppercase or lowercase English letters.

83. Word Search