龙岗义乌网站制作,it培训班大概需要多少钱,thinkphp旅游网站源码,网站建设合同属于什么合同LeetCode-79. 单词搜索【数组 字符串 回溯 矩阵】 题目描述#xff1a;解题思路一#xff1a;回溯 回溯三部曲。这里比较关键的是给board做标记#xff0c;防止之后搜索时重复访问。解题思路二#xff1a;回溯算法 dfs,直接看代码,很容易理解。visited哈希#xff0c;防止… LeetCode-79. 单词搜索【数组 字符串 回溯 矩阵】 题目描述解题思路一回溯 回溯三部曲。这里比较关键的是给board做标记防止之后搜索时重复访问。解题思路二回溯算法 dfs,直接看代码,很容易理解。visited哈希防止重复访问。解题思路三0 题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。
单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1 输入board [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word “ABCCED” 输出true 示例 2 输入board [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word “SEE” 输出true 示例 3 输入board [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word “ABCB” 输出false
提示
m board.length n board[i].length 1 m, n 6 1 word.length 15 board 和 word 仅由大小写英文字母组成
进阶你可以使用搜索剪枝的技术来优化解决方案使其在 board 更大的情况下可以更快解决问题
解题思路一回溯 回溯三部曲。这里比较关键的是给board做标记防止之后搜索时重复访问。 递归函数参数 这里的参数是 当前元素在矩阵 board 中的行列索引 i 和 j 当前目标字符在 word 中的索引 index 。 递归终止条件 返回 false (1) 行或列索引越界 或 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过 (3) 可合并至 (2) 。 返回 true k len(word) - 1 即字符串 word 已全部匹配。 单层搜索的逻辑 标记当前矩阵元素 将 board[i][j] 修改为 空字符 ‘’ 代表此元素已访问过防止之后搜索时重复访问。 搜索下一单元格 朝当前元素的 上、下、左、右 四个方向开启下层递归使用 或 连接 代表只需找到一条可行路径就直接返回不再做后续 DFS 并记录结果至 res 。 还原当前矩阵元素 将 board[i][j] 元素还原至初始值即 word[k] 。 返回值 返回布尔量 res 代表是否搜索到目标字符串。
使用空字符Python: ‘’ , Java/C: ‘\0’ 做标记是为了防止标记字符与矩阵原有字符重复。当存在重复时此算法会将矩阵原有字符认作标记字符从而出现错误。
class Solution:def __init__(self):self.dirs [(-1, 0), (0, 1), (1, 0), (0, -1)]def exist(self, board: List[List[str]], word: str) - bool:m, n len(board), len(board[0])for i in range(m):for j in range(n):if self.backtracking(board, i, j, 0, word):return Truereturn Falsedef backtracking(self, board, x, y, index, word):if x 0 or x len(board) or y 0 or y len(board[0]) or board[x][y] ! word[index]:return Falseif index len(word) - 1:return Trueres Falsefor d in self.dirs:nextx x d[0]nexty y d[1]board[x][y] res self.backtracking(board, nextx, nexty, index1, word) or resboard[x][y] word[index]return res在代码中M,N 分别为矩阵行列大小 K 为字符串 word 长度。
时间复杂度 O(3KMN) 最差情况下需要遍历矩阵中长度为 K 字符串的所有方案时间复杂度为 O(3K)矩阵中共有 MN 个起点时间复杂度为 O(MN) 。 方案数计算 设字符串长度为 K 搜索中每个字符有上、下、左、右四个方向可以选择舍弃回头上个字符的方向剩下 333 种选择因此方案数的复杂度为 O(3K)。 空间复杂度 O(K) 搜索过程中的递归深度不超过 K 因此系统因函数调用累计使用的栈空间占用 O(K) 因为函数返回后系统调用的栈空间会释放。最坏情况下 KMN递归深度为 MN 此时系统栈使用 O(MN) 的额外空间。
解题思路二回溯算法 dfs,直接看代码,很容易理解。visited哈希防止重复访问。
class Solution:def exist(self, board: List[List[str]], word: str) - bool:row len(board)col len(board[0])def helper(i, j, k, visited):#print(i,j, k,visited)if k len(word):return Truefor x, y in [(-1, 0), (1, 0), (0, 1), (0, -1)]:tmp_i x itmp_j y jif 0 tmp_i row and 0 tmp_j col and (tmp_i, tmp_j) not in visited \and board[tmp_i][tmp_j] word[k]:visited.add((tmp_i, tmp_j))if helper(tmp_i, tmp_j, k1, visited):return Truevisited.remove((tmp_i, tmp_j)) # 回溯return Falsefor i in range(row):for j in range(col):if board[i][j] word[0] and helper(i, j, 1,{(i, j)}) :return Truereturn False时间复杂度O(3KMN) 空间复杂度O(K)
解题思路三0 时间复杂度O(n) 空间复杂度O(n)
