想了解更多數(shù)據(jù)結(jié)構(gòu)以及算法題，可以關(guān)注微信公眾號“數(shù)據(jù)結(jié)構(gòu)和算法”，每天一題為你精彩解答。

問題描述

給定一個二維網(wǎng)格和一個單詞，找出該單詞是否存在于網(wǎng)格中。

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

示例:

board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]
給定 word = “ABCCED”, 返回 true
給定 word = “SEE”, 返回 true
給定 word = “ABCB”, 返回 false

提示：

• board 和 word 中只包含大寫和小寫英文字母。
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

回溯算法解決

這題是讓判斷給定的單詞是否在二維網(wǎng)格中，所以最簡單的一種方式就是使用dfs，沿著一個點往他的4個方向判斷，如果最后能找到給定的單詞就返回true，否則就返回false。

回溯算法實際上就是一個類似枚舉的搜索嘗試過程，也就是一個個去試，我們解這道題也是通過一個個去試，下面就用示例1來畫個圖看一下

他是從矩形中的一個點開始往他的上下左右四個方向查找，這個點可以是矩形中的任何一個點，所以代碼的大致輪廓我們應(yīng)該能寫出來，就是遍歷矩形所有的點，然后從這個點開始往他的4個方向走，因為是二維數(shù)組，所以有兩個for循環(huán)，代碼如下

public

這里關(guān)鍵代碼是dfs這個函數(shù)，因為每一個點都可以往他的4個方向查找，所以我們可以把它想象為一棵4叉樹，就是每個節(jié)點有4個子節(jié)點，而樹的遍歷我們最容易想到的就是遞歸，我們來大概看一下

boolean

最終的完整代碼如下

public

總結(jié)要想弄懂這題，首先要搞懂回溯算法，要想弄懂回溯算法，就要先要搞懂遞歸。關(guān)于遞歸和回溯算法之前有過詳細介紹，可以看下

450，什么叫回溯算法，一看就會，一寫就廢

426，什么是遞歸，通過這篇文章，讓你徹底搞懂遞歸

總結(jié)

以上是生活随笔為你收集整理的一个点是否在矩形内的算法_478，回溯算法解单词搜索的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。