Word Search

Medium

Given an m x n grid of characters board and a string word, return true if the word can be formed from sequentially adjacent (horizontally or vertically) cells, using each cell at most once.

Example 1

Input:  board = ["ABCE","SFCS","ADEE"], word = "ABCCED"
Output: true

Example 2

Input:  board = ["ABCE","SFCS","ADEE"], word = "ABCB"
Output: false

Constraints

• 1 <= m, n <= 6
• 1 <= word.length <= 15