Given a grid of letters and a target word, return true if the word exists in the grid.
You may move horizontally or vertically, and each cell may be used at most once in the path.
Build one partial choice at a time, recurse, then undo that choice before exploring the next option. Pay close attention to duplicate handling and stopping conditions.
Examples
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false
Constraints
- 1 <= board.length, board[0].length <= 6
- 1 <= word.length <= 15
- board and word contain English letters.