Determine whether a word exists in a letter grid

Given an m x n grid of characters board and a string word, determine whether word can be constructed from sequentially adjacent cells.

Rules:

• Adjacent cells are those horizontally or vertically neighboring (no diagonals).
• The same cell may not be used more than once in a single construction path.

Input

• board : 2D array of characters
• word : target string

Output

• Return true if word exists in the grid by the rules above, else false .

Example

board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = "ABCCED" → true

Constraints

• 1 ≤ m, n ≤ 12
• 1 ≤ |word| ≤ m*n