You are given a grid of letters, like a word puzzle. The grid is called board. You are also given a string word.
Return true if you can spell word by walking through the grid. Start at any cell. Each next letter must be in a cell right next to the last one: up, down, left or right (not diagonal). You cannot use the same cell two times in one word.
Examples
Example 1:
Input: board = [["C","A","T"],["O","R","S"],["W","E","N"]], word = "WORST"
Output: true
Explanation: W, O, R, S, T are connected one after the other: W(2,0), O(1,0), R(1,1), S(1,2), T(0,2).
Example 2:
Input: board = [["C","A","T"],["O","R","S"],["W","E","N"]], word = "ERE"
Output: false
Explanation: There is only one E in the grid, and a cell cannot be used twice.
Example 3:
Input: board = [["A","B"],["C","D"]], word = "ABCD"
Output: false
Explanation: B and C touch only at a corner. That is a diagonal step, which is not allowed.