1000ms

Difficulty: 4

算法标签>

DFS

Leetcode 60.单词搜索-原题链接

题目内容

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

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

输入格式

第一行包含两个正整数 (m) 和 (n)，分别表示网格的行数和列数。
接下来 (m) 行，每行包含 (n) 个字符，中间以空格分隔，表示二维字符网格 board。
最后一行包含一个字符串 word。

输出格式

如果单词 word 在网格中存在，则输出 true；否则，输出 false。

样例输入1

3 4
A B C E
S F C S
A D E E
ABCCED

样例输出1

true

样例输入2

3 4
A B C E
S F C S
A D E E
SEE

样例输出2

true

样例输入3

3 4
A B C E
S F C S
A D E E
ABCB

样例输出3

false

提示：

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