單詞搜索

題目描述：給定一個 m x n 二維字符網(wǎng)格 board 和一個字符串單詞 word 。如果 word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。

單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允許被重復(fù)使用。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

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

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：回溯算法

首先，直接判斷2種特殊場景：

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

• 如果board數(shù)組為空，直接返回false。

否則，先聲明一個和board同樣大小的boolean類型的數(shù)組，記錄當(dāng)前單元格是否已經(jīng)走過，然后遍歷board的每一個字符，對每一個字符和word第一個字符相等的時候，調(diào)用回溯方法進行判斷以當(dāng)前字符為起點是否能夠匹配word字符串，如果能返回true，否則繼續(xù)遍歷下一個字符。最后，如果沒有匹配成功，返回false。

【每日寄語】 逆境、是非來臨，心中要持一“寬”字。