【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
目录
相关文章
|
18天前
|
缓存 供应链 监控
1688item_search_factory - 按关键字搜索工厂数据接口深度分析及 Python 实现
item_search_factory接口专为B2B电商供应链优化设计,支持通过关键词精准检索工厂信息,涵盖资质、产能、地理位置等核心数据,助力企业高效开发货源、分析产业集群与评估供应商。
|
20天前
|
JSON 监控 数据格式
1688 item_search_app 关键字搜索商品接口深度分析及 Python 实现
1688开放平台item_search_app接口专为移动端优化,支持关键词搜索、多维度筛选与排序,可获取商品详情及供应商信息,适用于货源采集、价格监控与竞品分析,助力采购决策。
|
2月前
|
缓存 API 网络架构
淘宝item_search_similar - 搜索相似的商品API接口,用python返回数据
淘宝联盟开放平台中,可通过“物料优选接口”(taobao.tbk.dg.optimus.material)实现“搜索相似商品”功能。该接口支持根据商品 ID 获取相似推荐商品,并返回商品信息、价格、优惠等数据,适用于商品推荐、比价等场景。本文提供基于 Python 的实现示例,包含接口调用、数据解析及结果展示。使用时需配置淘宝联盟的 appkey、appsecret 和 adzone_id,并注意接口调用频率限制和使用规范。
|
21天前
|
缓存 供应链 监控
VVIC seller_search 排行榜搜索接口深度分析及 Python 实现
VVIC搜款网seller_search接口提供服装批发市场的商品及商家排行榜数据,涵盖热销榜、销量排名、类目趋势等,支持多维度筛选与数据分析,助力选品决策、竞品分析与市场预测,为服装供应链提供有力数据支撑。
|
11天前
|
缓存 监控 算法
唯品会item_search - 按关键字搜索 VIP 商品接口深度分析及 Python 实现
唯品会item_search接口支持通过关键词、分类、价格等条件检索商品,广泛应用于电商数据分析、竞品监控与市场调研。结合Python可实现搜索、分析、可视化及数据导出,助力精准决策。
|
11天前
|
缓存 监控 算法
苏宁item_search - 按关键字搜索商品接口深度分析及 Python 实现
苏宁item_search接口支持通过关键词、分类、价格等条件检索商品,广泛应用于电商分析、竞品监控等场景。具备多维度筛选、分页获取、数据丰富等特性,结合Python可实现搜索、分析与可视化,助力市场研究与决策。
|
2月前
|
机器学习/深度学习 算法 文件存储
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
神经架构搜索(NAS)正被广泛应用于大模型及语言/视觉模型设计,如LangVision-LoRA-NAS、Jet-Nemotron等。本文回顾NAS核心技术,解析其自动化设计原理,探讨强化学习、进化算法与梯度方法的应用与差异,揭示NAS在大模型时代的潜力与挑战。
312 6
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
|
29天前
|
Web App开发 缓存 监控
微店店铺商品搜索(item_search_shop)接口深度分析及 Python 实现
item_search_shop接口用于获取特定店铺的全部商品数据,支持批量获取商品列表、基础信息、价格、销量等,适用于竞品监控、商品归类及店铺分析等场景,助力全面了解店铺经营状况。
|
10天前
|
JSON 缓存 供应链
电子元件 item_search - 按关键字搜索商品接口深度分析及 Python 实现
本文深入解析电子元件item_search接口的设计逻辑与Python实现,涵盖参数化筛选、技术指标匹配、供应链属性过滤及替代型号推荐等核心功能,助力高效精准的电子元器件搜索与采购决策。
|
16天前
|
缓存 自然语言处理 算法
item_search - Lazada 按关键字搜索商品接口深度分析及 Python 实现
Lazada的item_search接口是关键词搜索商品的核心工具,支持多语言、多站点,可获取商品价格、销量、评分等数据,适用于市场调研与竞品分析。

热门文章

最新文章

推荐镜像

更多