Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same cell may not be used more than once.

Examples

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

Explanation: The word "ABCCED" can be traced starting from the top-left 'A', moving right to 'B', right to 'C', down to 'C', left to 'E' (but actually down to 'E'), then left to 'D'.

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Output: true

Explanation: The word "SEE" can be found starting from 'S' at position (1,3), moving down to 'E' at (2,3), then left to 'E' at (2,2).

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

Output: false

Explanation: The path for "ABC" exists, but 'B' at (0,1) was already used and cannot be revisited.

Constraints

• m == board.length
• n == board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consist of only lowercase and uppercase English letters