单词搜索

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

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

示例说明请见LeetCode官网。

来源：力扣（LeetCode）   

链接：https://leetcode-cn.com/problems/word-search/   

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：回溯算法

首先，直接判断2种特殊场景：

• 如果要匹配的字符串为空，直接返回true；

• 如果board数组为空，直接返回false。

否则，先声明一个和board同样大小的boolean类型的数组，记录当前单元格是否已经走过，然后遍历board的每一个字符，对每一个字符和word第一个字符相等的时候，调用回溯方法进行判断以当前字符为起点是否能够匹配word字符串，如果能返回true，否则继续遍历下一个字符。最后，如果没有匹配成功，返回false。

【每日寄语】 逆境、是非来临，心中要持一“宽”字。