LeetCode-79. 单词搜索【数组 字符串 回溯 矩阵】
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, index+1, 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) (因为函数返回后,系统调用的栈空间会释放)。最坏情况下 K=MN,递归深度为 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, k+1, 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)
相关文章:
LeetCode-79. 单词搜索【数组 字符串 回溯 矩阵】
LeetCode-79. 单词搜索【数组 字符串 回溯 矩阵】 题目描述:解题思路一:回溯 回溯三部曲。这里比较关键的是给board做标记,防止之后搜索时重复访问。解题思路二:回溯算法 dfs,直接看代码,很容易理解。visited哈希,防止…...
游戏引擎之高级动画技术
一、动画混合 当我们拥有各类动画素材(clips)时,要将它们融合起来成为一套完整的动画。 最经典的例子就是从走的动画自然的过渡到跑的动画。 1.1 线性插值 不同于上节课的LERP(同一个clip内不同pose之间)ÿ…...
Oracle 数据库中的全文搜索
Oracle 数据库中的全文搜索 0. 引言1. 整体流程2. 创建索引2-1. 创建一个简单的表2-2. 创建文本索引2-3. 查看创建的基础表 3. 运行查询3-1. 运行文本查询3-2. CONTAINS 运算符3-3. 混合查询3-4. OR 查询3-5. 通配符3-6. 短语搜索3-7. 模糊搜索(Fuzzy searches&…...
代码随想录阅读笔记-二叉树【二叉搜索树中的众数】
题目 给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。 假定 BST 有如下定义: 结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的…...
AcWing-游戏
1388. 游戏 - AcWing题库 所需知识:博弈论,区间dp 由于双方都采取最优的策略来取数字,所以结果为确定的,有可能会有多个不同的过程,但是我们只需要关注最终结果就行了。 方法一: 定义dp[i][j] 表示区间…...
Mybatis——一对一映射
一对一映射 预置条件 在某网络购物系统中,一个用户只能拥有一个购物车,用户与购物车的关系可以设计为一对一关系 数据库表结构(唯一外键关联) 创建两个实体类和映射接口 package org.example.demo;import lombok.Data;import …...
Web 安全之 SSL 剥离攻击详解
目录 SSL/TLS简介 SSL 剥离攻击原理 SSL 剥离攻击的影响 SSL 剥离攻击的防范措施 小结 SSL 剥离攻击(SSL Stripping Attack)是一种针对安全套接层(SSL)或传输层安全性(TLS)协议的攻击手段,…...
数据结构——顺序表(C语言)
目录 一、顺序表概念 二、顺序表分类 1.静态顺序表 2.动态顺序表 三、顺序表的实现 1.顺序表的结构体定义 2. 顺序表初始化 3.顺序表销毁 4.顺序表的检验 5.顺序表打印 6.顺序表扩容 7.顺序表尾插与头插 8.尾删与头删 9.在pos处插入数据 10.在pos处删除数据 11.查找数据 …...
利用Idea实现Ajax登录(maven工程)
一、新建一个maven工程(不会建的小伙伴可以参考Idea引入maven工程依赖(保姆级)-CSDN博客),工程目录如图 js文件可以上up网盘提取 链接:https://pan.baidu.com/s/1yOFtiZBWGJY64fa2tM9CYg?pwd5555 提取码&…...
环信IM集成教程——Web端UIKit快速集成与消息发送
写在前面: 千呼万唤始出来,环信Web端终于出UIKit了!🎉🎉🎉 文档地址:https://doc.easemob.com/uikit/chatuikit/web/chatuikit_overview.html 环信单群聊 UIKit 是基于环信即时通讯云 IM SDK 开…...
Anaconda如何切换国内镜像源
一、anaconda如何切换阿里镜像源 在Anaconda中切换到阿里云镜像源可以通过以下步骤进行: 1、打开终端(Windows)或者命令行界面(macOS/Linux)。 2、执行以下命令来配置阿里云镜像源: conda config --add…...
Android 14.0 添加自定义服务,并生成jar给第三方app调用
1.概述 在14.0系统ROM产品定制化开发中,由于需要新增加自定义的功能,所以要增加自定义服务,而app上层通过调用自定义服务,来调用相应的功能,所以系统需要先生成jar,然后生成jar 给上层app调用,接下来就来分析实现的步骤,然后来实现相关的功能 从而来实现所需要的功能 …...
解决沁恒ch592单片机在tmos中使用USB总线时,接入USB Hub无法枚举频繁Reset的问题
开发产品时采用了沁恒ch592,做USB开发时遇到了一个奇葩的无法枚举问题。 典型症状 使用USB线直连电脑时没有问题,可以正常使用。 如果接入某些特定方案的USB Hub(例如GL3510、GL3520),可能会出现以下2种情况…...
nvm保姆级安装使用教程
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: 开发环境篇 ✨特色专栏: M…...
大语言模型LLM《提示词工程指南》学习笔记02
文章目录 大语言模型LLM《提示词工程指南》学习笔记02设计提示时需要记住的一些技巧零样本提示少样本提示链式思考(CoT)提示自我一致性生成知识提示 大语言模型LLM《提示词工程指南》学习笔记02 设计提示时需要记住的一些技巧 指令 您可以使用命令来指…...
【realme x2手机解锁BootLoader(简称BL)】
realme手机解锁常识 https://www.realme.com/cn/support/kw/doc/2031665 realme手机解锁支持型号 https://www.realmebbs.com/post-details/1275426081138028544 realme x2手机解锁实践 参考:https://www.realmebbs.com/post-details/1255473809142591488 1 下载apk…...
攻防世界 wife_wife
在这个 JavaScript 示例中,有两个对象:baseUser 和 user。 baseUser 对象定义如下: baseUser { a: 1 } 这个对象有一个属性 a,其值为 1,没有显式指定原型对象,因此它将默认继承 Object.prototype。 …...
Visual Studio安装下载进度为零已解决
因为在安装pytorch3d0.3.0时遇到问题,提示没有cl.exe,VS的C编译组件,可以添加组件也可以重装VS。查了下2019版比2022问题少,选择了安装2019版,下面是下载安装时遇到的问题记录,关于下载进度为零网上有三类解…...
矩阵空间秩1矩阵小世界图
文章目录 1. 矩阵空间2. 微分方程3. 秩为1的矩阵4. 图 1. 矩阵空间 我们以3X3的矩阵空间 M 为例来说明相关情况。目前矩阵空间M中只关心两类计算,矩阵加法和矩阵数乘。 对称矩阵-子空间-有6个3X3的对称矩阵,所以为6维矩阵空间上三角矩阵-子空间-有6个3…...
《QT实用小工具·十三》FlatUI辅助类之各种炫酷的控件集合
1、概述 源码放在文章末尾 FlatUI辅助类之各种炫酷的控件集合 按钮样式设置。文本框样式设置。进度条样式。滑块条样式。单选框样式。滚动条样式。可自由设置对象的高度宽度大小等。自带默认参数值。 下面是demo演示: 项目部分代码如下所示: #ifnd…...
dm8 备份与恢复
dm8 备份与恢复 基础环境 操作系统:Red Hat Enterprise Linux Server release 7.9 (Maipo) 数据库版本:DM Database Server 64 V8 架构:单实例1 设置bak_path路径 --创建备份文件存放目录 su - dmdba mkdir -p /dm8/backup--修改dm.ini 文件…...
Vue项目中引入html页面(vue.js中引入echarts数据大屏html [静态非数据传递!] )
在项目原有vue(例如首页)基础上引入html页面 1、存放位置 vue3原有public文件夹下 我这边是新建一个static文件夹 专门存放要用到的html文件 复制拖拽过来 index为html的首页 2、更改路径引入到vue中 这里用到的是 iframe 方法 不同于vue的 component…...
ASTM C1186-22 纤维水泥平板
以无石棉类无机矿物纤维、有机合成纤维或纤维素纤维,单独或混合作为增强材料,以普通硅酸盐水泥或水泥中添加硅质、钙质材料代替部分水泥为胶凝材料,经制浆、成型、蒸汽或高压蒸汽养护制成的板材,俗称水泥压力板。 ASTM C1186-22纤…...
NoSQL概述
NoSQL概述 目录 一、为什么用NoSQL 二、什么是NoSQL 三、经典应用分析 四、N o S Q L 数 据 模 型 简 介 五、NoSQL四大分类 六、CAP BASE 一、为什么用NoSQL 1、单机MySQL的美好年代 在90年代,一个网站的访问量一般不大,用单个数据库完全可以轻松应…...
爬虫实战一、Scrapy开发环境(Win10+Anaconda3)搭建
#前言 在这儿推荐使用Anaconda进行安装,并不推荐大家用pythonpip安装,因为pythonpip的坑实在是太多了。 #一、环境中准备: Win10(企业版)Anaconda3-5.0.1-Windows-x86_64,下载地址,如果打不开…...
llama.cpp运行qwen0.5B
编译llama.cp 参考 下载模型 05b模型下载 转化模型 创建虚拟环境 conda create --prefixD:\miniconda3\envs\llamacpp python3.10 conda activate D:\miniconda3\envs\llamacpp安装所需要的包 cd G:\Cpp\llama.cpp-master pip install -r requirements.txt python conver…...
【接口】HTTP(3) |GET和POST两种基本请求方法有什么区别
在我面试时,在我招人面试别人时,10次能遇到7次这个问题,我听过我也说回答过: Get: 一般对于从服务器取数据的请求可以设置为get方式 Get方式在传递参数的时候,一般都会把参数直接拼接在url上 Get请求方法…...
金陵科技学院软件工程学院软件工程专业
感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦~~ 感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦~~ 感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦~~ 感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦…...
Android 关于apk反编译d2j-dex2jar classes.dex失败的几种方法
目录 确认路径正确直接定位到指定目录确定目录正确,按如下路径修改下面是未找到相关文件正确操作 确认路径正确 ,即d2j-dex2jar和classes.dex是否都在一个文件夹里(大部分的情况都是路径不正确) 直接定位到指定目录 路径正确的…...
Django--admin 后台管理站点
Django最大的优点之一,就是体贴的提供了一个基于项目model创建的一个后台管理站点admin。这个界面只给站点管理员使用,并不对大众开放。虽然admin的界面可能不是那么美观,功能不是那么强大,内容不一定符合你的要求,但是…...
广东省江门开平疫情最新消息/长春seo整站优化
自从接触 IOptions 之后,一直纠结这样的问题:自己定义的 Options 要不要实现 IOptions 接口。 微软有的项目中实现了,比如 Caching 中的 MemoryCacheOptions : public class MemoryCacheOptions : IOptions<MemoryCacheOptions…...
做母婴产品哪个网站做的好处/全免费建立自己的网站
docker框架系列教程已经到第七期了,今天我们介绍一下Dockerfile镜像的创建,重点都在内部进行了标注,喜欢记得分享收藏。 Dockerfile创建镜像 Dockerfile由一行行命令语句组成,并且支持用“#”开头作为注释,一般的&…...
类似pinterest的网站/东莞seo黑帽培训
PetaPoco是一种轻量级的ORM框架,可同时运行在.net与mono平台上; 一.PetaPoco如何使用两个以上的数据库? 在PetaPoco中有一个SingleDbFactory的仓储类,她负责取得链接数据库字符串的KEY,所以,想要在一个数据…...
淘客手机端网站建设/客服外包
不会敲代码,怎么学也不会,那怎么做大数据智能分析?说来也简单,用商业智能BI软件就行。拖拉拽就能做报表,点击即可智能分析,即使是没有IT基础,完全不会敲代码的人也能轻松抽取数据做智能分析。商…...
帝国cms建设 政府网站/搜索引擎网站排名优化方案
一、引言 Mybatis可以直接传入一个集合,通过标签将集合中的数据遍历出来实现批量新增 不同的数据库批量新增有区别,如下实现两种方式的批量新增 二、实现 2.1映射文件 <!--单条插入 --><insert id"insertOne" parameterType"…...
如果做网站报价/新网站如何推广
一.实验需求:1.完成下方的企业网络配置;2.完成上方的运营商网络配置;3.企业网络与ISP网络的互联IP地址,如图配置;4.企业网络 OSPF 多区域设置,如图配置;5.区域 10 中的 PC-1/2属于 v…...