给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
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/video/av25763384?t=813
熟悉的同学直接看代码吧
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;
}
}
class Solution:
def dfs(self, board, word, index, x, y):
if not board or index == len(word):
return True
if x < 0 or x == len(board) or y < 0 or y == len(board[0]):
return False
if board[x][y] != word[index]:
return False
source = 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] = source
return exist
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if len(word) == 0:
return False
for i in range(len(board)):
for j in range(len(board[0])):
if self.dfs(board, word, 0, i, j):
return True
return False
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.