福建省住房城乡建设部网站,99作文网,商业网站的创建程序,网站ipv6改造怎么做文章目录 题目描述思路分析完整代码 题目描述 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构成#xff… 文章目录 题目描述思路分析完整代码 题目描述 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。 单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 例如在下面的 3×4 的矩阵中包含单词 “ABCCED”单词中的字母已标出。 示例 1 输入board [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word “ABCCED” 输出true 示例 2 输入board [[“a”,“b”],[“c”,“d”]], word “abcd” 输出false 思路分析
一道非常经典的矩阵搜索题。
直接回溯。
1.确定循环体
肯定是要遍历矩阵中的每一个格子以每一个格子为起点向外搜索。
for i in range(len(board)):for j in range(len(board[0])):
2.确定回溯体参数
显然需要当前遍历的格子下标i和j还需要当前遍历的单词下标k。 def dfs(i,j,k):
3.确定回溯体
在回溯的过程中如果遇到边界则立即回退遇到不符合单词的字符也立即回退。
if not 0ilen(board) or not 0 jlen(board[0]) or board[i][j] ! word[k]:return False 当前遍历单词的下标k如果遍历到最后了说明此时找到了完整的单词
if len(word)-1 k:return True
后面就是连续的三步 1首先将所有遍历过的格子都弄成空防止重复遍历。 2. 回溯寻找当前格子的四周。 3. 回退的时候将变空的格子变回原来的数值。 board[i][j] res dfs(i-1,j,k1) or dfs(i,j-1,k1) or dfs(i1,j,k1) or dfs(i,j1,k1)board[i][j] word[k]完整代码
class Solution:def exist(self, board: List[List[str]], word: str) - bool:# k为当前word遍历的下标def dfs(i,j,k):if not 0ilen(board) or not 0 jlen(board[0]) or board[i][j] ! word[k]:return Falseif len(word)-1 k:return Trueboard[i][j] res dfs(i-1,j,k1) or dfs(i,j-1,k1) or dfs(i1,j,k1) or dfs(i,j1,k1)board[i][j] word[k]return res for i in range(len(board)):for j in range(len(board[0])):if dfs(i,j,0):return Truereturn False
