題目

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

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

示例:

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

給定 word = "ABCCED", 返回 true.
給定 word = "SEE", 返回 true.
給定 word = "ABCB", 返回 false.

題解

這個題目拿到題目就應該能想到是用DFS的題目，因為這完完全全就是DFS，沒有做任何的變形，關于DFS，這里就不重復講解。

推薦一個b站上的視頻，不熟悉的同學可以回顧一下。

https://www.bilibili.com/vide...

熟悉的同學直接看代碼吧

java

class Solution {public boolean exist(char[][] board, String word) {if (word == null || word.length() == 0) {return true;}char[] chs = word.toCharArray();for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (dfs(board, chs, 0, i, j)) {return true;}}}return false;}private boolean dfs(char[][] board, char[] words, int index, int x, int y) {if (index == words.length) {return true;}if (x < 0 || x == board.length || y < 0 || y == board[0].length) {return false;}if (board[x][y] != words[index]) {return false;}char source = board[x][y];board[x][y] = '\0';boolean exist = dfs(board, words, index + 1, x, y + 1)|| dfs(board, words, index + 1, x, y - 1)|| dfs(board, words, index + 1, x + 1, y)|| dfs(board, words, index + 1, x - 1, y);board[x][y] = source;return exist;} }

python

class Solution:def dfs(self, board, word, index, x, y):if not board or index == len(word):return Trueif x < 0 or x == len(board) or y < 0 or y == len(board[0]):return Falseif board[x][y] != word[index]:return Falsesource = board[x][y]board[x][y] = '\0'exist = self.dfs(board, word, index + 1, x, y + 1) or self.dfs(board, word, index + 1, x, y - 1) or self.dfs(board, word, index + 1, x + 1, y) or self.dfs(board, word, index + 1, x - 1, y)board[x][y] = sourcereturn existdef exist(self, board, word):""":type board: List[List[str]]:type word: str:rtype: bool"""if len(word) == 0:return Falsefor i in range(len(board)):for j in range(len(board[0])):if self.dfs(board, word, 0, i, j):return Truereturn False

熱門閱讀

• MySQL索引背后的數據結構及算法原理
• 【Leetcode】78. 子集
• 【Leetcode】77. 組合

總結

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

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