【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径

简介: Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。

1 题目

给定一个 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 仅由大小写英文字母组成

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2 解析

使用回溯算法
设函数 check(i,j,k) 表示判断以网格的 (i, j)位置出发,能否搜索到单词word[k…],其中 word[k…] 表示字符串word 从第 k 个字符开始的后缀子串。如果能搜索到,则返回true,反之返回 false。函数 check(i,j,k) 的执行步骤如下:

  • 如果 board [ i ] [ j ] ≠ s [ k ] \textit{board}[i][j] \neq s[k] board[i][j]\=s[k],当前字符不匹配,直接返回 False。
  • 如果当前已经访问到字符串的末尾,且对应字符依然匹配,此时直接返回 True。
  • 否则,遍历当前位置的所有相邻位置。如果从某个相邻位置出发,能够搜索到子串 word[k+1…],则返回True,否则返回False。
    这样,我们对每一个位置(i,j) 都调用函数 check(i,j,0) 进行检查:只要有一处返回 True,就说明网格中能够找到相应的单词,否则说明不能找到。

为了防止重复遍历相同的位置,需要额外维护一个与 board 等大的visited 数组,用于标识每个位置是否被访问过。每次遍历相邻位置时,需要跳过已经被访问的位置。

作者:LeetCode-Solution
链接:https://leetcode.cn/problems/word-search/solution/dan-ci-sou-suo-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

3 python实现

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:

        direction = [(0,1),(0,-1),(1,0),(-1,0)]
        visited = set()
        def check(i,j,k):
            if board[i][j]!=word[k]:
                return False
            if len(word)-1==k:
                return True

            visited.add((i,j))
            res = False
            for di,dj in direction:
                x,y = di+i,dj+j
                if 0<=x<len(board) and 0<=y<len(board[0]):
                    if (x,y) not in visited:
                        if check(x,y,k+1):
                            res =  True
                            break
            # 回溯
            visited.remove((i,j))
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if check(i,j,0):
                    return True

        return False
目录
相关文章
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
104 0
|
5月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
273 14
|
6月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
138 4
|
6月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
158 10
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
99 0
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
93 2
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
103 0
Leetcode第三十三题(搜索旋转排序数组)
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
87 0
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
93 0
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
211 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行

推荐镜像

更多