这是一个创建于 2637 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
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
熟悉的同学直接看代码吧
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 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 热门阅读
目前尚无回复
Select Language