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

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

?

示例:

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

DFS+回溯

看到二維表就想到DFS，遍歷整個二維表，當前位置為word開頭字母時才執行DFS，同時還要加一個vis數組表示已訪問的位置，然后加一些判斷條件剪枝。

Code

def exist(self, board: List[List[str]], word: str) -> bool:def dfs(x, y, tmp):nonlocal flagif tmp == word:flag = Truereturnif not (0 <= x < rowLength and 0 <= y < colLength):returnif flag or vis[x][y] or board[x][y] != word[len(tmp)]:returnvis[x][y] = Truedfs(x + 1, y, tmp + board[x][y])dfs(x - 1, y, tmp + board[x][y])dfs(x, y + 1, tmp + board[x][y])dfs(x, y - 1, tmp + board[x][y])vis[x][y] = FalserowLength, colLength, flag = len(board), len(board[0]), Falsevis = [[False for _ in range(colLength)] for _ in range(rowLength)]for i in range(rowLength):for j in range(colLength):if board[i][j] == word[0]:dfs(i, j, '')if flag:return flagreturn flag

總結

以上是生活随笔為你收集整理的79. Word Search 单词搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。