759. Word Search in 2D Grid

Given an m x n character grid board and a string word, return true if the word exists in the grid. The word is constructed from letters of adjacent cells (horizontally or vertically neighboring). The SAME cell may NOT be used more than once within a single word. The input is provided as a JSON object with two fields: board (array of rows, each a list of single-character strings) and word (a string).

Input: A JSON object: {"board": [[...]], "word": "..."}.

Output: Return a boolean: true or false (lowercase).

Examples

Input: {"board":[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"word":"ABCCED"}
Output: true
Explanation: Path A->B->C->C->E->D exists going right, right, down, down-left, left.

Input: {"board":[["A","B"],["C","D"]],"word":"AC"}
Output: true
Explanation: A at (0,0) then C at (1,0) (down).

Input: {"board":[["A","B"],["C","D"]],"word":"ABCD"}
Output: false
Explanation: Cannot form ABCD without revisiting cells.

Constraints

• 1 <= m, n <= 5
• 1 <= word.length <= 10
• board[i][j] is a single uppercase English letter A-Z
• word consists of uppercase English letters A-Z

Asked by