单词搜索

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

单词必须按照字母顺序，由相邻单元格内的字母构成。"相邻"单元格指水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

约定

• board 仅由小写英文字母组成。
• word 仅由小写英文字母组成。
• 你可以从任意位置出发，向上下左右四个方向扩展。
• 一条路径上的格子不能重复经过。

输入

• board：二维字符数组，1 <= m, n <= 6
• word：字符串，1 <= word.length <= 15

输出

布尔值：若 word 能在 board 中按相邻格子拼出，返回 true，否则返回 false。

示例一

输入：

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

输出：

true

解释：沿 (0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,1) 可拼出 ABCCED。

示例二

输入：

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

输出：

true

示例三

输入：

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

输出：

false

复杂度要求

• 时间复杂度上界约 O(m·n·3^L)，其中 L 为单词长度。
• 空间复杂度 O(L)，为递归栈深度。