题目描述

给定一个 $m \times n$ 二维字符网格 $board$ 和一个字符串单词 $word$ 。如果 $word$ 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

输入格式

第一行两个整数表示 $m$ $n$；

接下来的 $m$ 行，每行 $n$ 个字符表示 $board$ 中的各元素字母。

最后一行一个字符串表示单词 $word$。

输出格式

返回 'true' 或 'false' 表示答案。

示例 1：

3 4
ABCE
SFCS
ADEE
ABCCED

true

示例 2：

3 4
ABCE
SFCS
ADEE
SEE

true

示例 3：

3 4
ABCE
SFCS
ADEE
ABCB

false

所有样例下载

提示：

• $m == board.length$
• $n = board[i].length$
• $1 <= m, n <= 6$
• $1 <= word.length <= 15$
• $board$ 和 $word$ 仅由大小写英文字母组成

进阶： 你可以使用搜索剪枝的技术来优化解决方案，使其在 $board$ 更大的情况下可以更快解决问题？

SOURCE

单词搜索