当前位置: 首页 > news >正文

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做标记,防止之后搜索时重复访问。

  1. 递归函数参数
    这里的参数是:
    当前元素在矩阵 board 中的行列索引 i 和 j ,当前目标字符在 word 中的索引 index 。

  2. 递归终止条件
    返回 false: (1) 行或列索引越界 或 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过 ( (3) 可合并至 (2) ) 。
    返回 true : k = len(word) - 1 ,即字符串 word 已全部匹配。

  3. 单层搜索的逻辑
    标记当前矩阵元素: 将 board[i][j] 修改为 空字符 ‘’ ,代表此元素已访问过,防止之后搜索时重复访问。
    搜索下一单元格: 朝当前元素的 上、下、左、右 四个方向开启下层递归,使用 或 连接 (代表只需找到一条可行路径就直接返回,不再做后续 DFS ),并记录结果至 res 。
    还原当前矩阵元素: 将 board[i][j] 元素还原至初始值,即 word[k] 。

  4. 返回值: 返回布尔量 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. 单词搜索【数组 字符串 回溯 矩阵】 题目描述&#xff1a;解题思路一&#xff1a;回溯 回溯三部曲。这里比较关键的是给board做标记&#xff0c;防止之后搜索时重复访问。解题思路二&#xff1a;回溯算法 dfs,直接看代码,很容易理解。visited哈希&#xff0c;防止…...

游戏引擎之高级动画技术

一、动画混合 当我们拥有各类动画素材&#xff08;clips&#xff09;时&#xff0c;要将它们融合起来成为一套完整的动画。 最经典的例子就是从走的动画自然的过渡到跑的动画。 1.1 线性插值 不同于上节课的LERP&#xff08;同一个clip内不同pose之间&#xff09;&#xff…...

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. 模糊搜索&#xff08;Fuzzy searches&…...

代码随想录阅读笔记-二叉树【二叉搜索树中的众数】

题目 给定一个有相同值的二叉搜索树&#xff08;BST&#xff09;&#xff0c;找出 BST 中的所有众数&#xff08;出现频率最高的元素&#xff09;。 假定 BST 有如下定义&#xff1a; 结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的…...

AcWing-游戏

1388. 游戏 - AcWing题库 所需知识&#xff1a;博弈论&#xff0c;区间dp 由于双方都采取最优的策略来取数字&#xff0c;所以结果为确定的&#xff0c;有可能会有多个不同的过程&#xff0c;但是我们只需要关注最终结果就行了。 方法一&#xff1a; 定义dp[i][j] 表示区间…...

Mybatis——一对一映射

一对一映射 预置条件 在某网络购物系统中&#xff0c;一个用户只能拥有一个购物车&#xff0c;用户与购物车的关系可以设计为一对一关系 数据库表结构&#xff08;唯一外键关联&#xff09; 创建两个实体类和映射接口 package org.example.demo;import lombok.Data;import …...

Web 安全之 SSL 剥离攻击详解

目录 SSL/TLS简介 SSL 剥离攻击原理 SSL 剥离攻击的影响 SSL 剥离攻击的防范措施 小结 SSL 剥离攻击&#xff08;SSL Stripping Attack&#xff09;是一种针对安全套接层&#xff08;SSL&#xff09;或传输层安全性&#xff08;TLS&#xff09;协议的攻击手段&#xff0c;…...

数据结构——顺序表(C语言)

目录 一、顺序表概念 二、顺序表分类 1.静态顺序表 2.动态顺序表 三、顺序表的实现 1.顺序表的结构体定义 2. 顺序表初始化 3.顺序表销毁 4.顺序表的检验 5.顺序表打印 6.顺序表扩容 7.顺序表尾插与头插 8.尾删与头删 9.在pos处插入数据 10.在pos处删除数据 11.查找数据 …...

利用Idea实现Ajax登录(maven工程)

一、新建一个maven工程&#xff08;不会建的小伙伴可以参考Idea引入maven工程依赖(保姆级)-CSDN博客&#xff09;&#xff0c;工程目录如图 ​​​​​​​ js文件可以上up网盘提取 链接&#xff1a;https://pan.baidu.com/s/1yOFtiZBWGJY64fa2tM9CYg?pwd5555 提取码&…...

环信IM集成教程——Web端UIKit快速集成与消息发送

写在前面&#xff1a; 千呼万唤始出来&#xff0c;环信Web端终于出UIKit了&#xff01;&#x1f389;&#x1f389;&#x1f389; 文档地址&#xff1a;https://doc.easemob.com/uikit/chatuikit/web/chatuikit_overview.html 环信单群聊 UIKit 是基于环信即时通讯云 IM SDK 开…...

Anaconda如何切换国内镜像源

一、anaconda如何切换阿里镜像源 在Anaconda中切换到阿里云镜像源可以通过以下步骤进行&#xff1a; 1、打开终端&#xff08;Windows&#xff09;或者命令行界面&#xff08;macOS/Linux&#xff09;。 2、执行以下命令来配置阿里云镜像源&#xff1a; conda config --add…...

Android 14.0 添加自定义服务,并生成jar给第三方app调用

1.概述 在14.0系统ROM产品定制化开发中,由于需要新增加自定义的功能,所以要增加自定义服务,而app上层通过调用自定义服务,来调用相应的功能,所以系统需要先生成jar,然后生成jar 给上层app调用,接下来就来分析实现的步骤,然后来实现相关的功能 从而来实现所需要的功能 …...

解决沁恒ch592单片机在tmos中使用USB总线时,接入USB Hub无法枚举频繁Reset的问题

开发产品时采用了沁恒ch592&#xff0c;做USB开发时遇到了一个奇葩的无法枚举问题。 典型症状 使用USB线直连电脑时没有问题&#xff0c;可以正常使用。 如果接入某些特定方案的USB Hub&#xff08;例如GL3510、GL3520&#xff09;&#xff0c;可能会出现以下2种情况&#xf…...

nvm保姆级安装使用教程

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; 开发环境篇 ✨特色专栏&#xff1a; M…...

大语言模型LLM《提示词工程指南》学习笔记02

文章目录 大语言模型LLM《提示词工程指南》学习笔记02设计提示时需要记住的一些技巧零样本提示少样本提示链式思考&#xff08;CoT&#xff09;提示自我一致性生成知识提示 大语言模型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手机解锁实践 参考&#xff1a;https://www.realmebbs.com/post-details/1255473809142591488 1 下载apk…...

攻防世界 wife_wife

在这个 JavaScript 示例中&#xff0c;有两个对象&#xff1a;baseUser 和 user。 baseUser 对象定义如下&#xff1a; baseUser { a: 1 } 这个对象有一个属性 a&#xff0c;其值为 1&#xff0c;没有显式指定原型对象&#xff0c;因此它将默认继承 Object.prototype。 …...

Visual Studio安装下载进度为零已解决

因为在安装pytorch3d0.3.0时遇到问题&#xff0c;提示没有cl.exe&#xff0c;VS的C编译组件&#xff0c;可以添加组件也可以重装VS。查了下2019版比2022问题少&#xff0c;选择了安装2019版&#xff0c;下面是下载安装时遇到的问题记录&#xff0c;关于下载进度为零网上有三类解…...

矩阵空间秩1矩阵小世界图

文章目录 1. 矩阵空间2. 微分方程3. 秩为1的矩阵4. 图 1. 矩阵空间 我们以3X3的矩阵空间 M 为例来说明相关情况。目前矩阵空间M中只关心两类计算&#xff0c;矩阵加法和矩阵数乘。 对称矩阵-子空间-有6个3X3的对称矩阵&#xff0c;所以为6维矩阵空间上三角矩阵-子空间-有6个3…...

《QT实用小工具·十三》FlatUI辅助类之各种炫酷的控件集合

1、概述 源码放在文章末尾 FlatUI辅助类之各种炫酷的控件集合 按钮样式设置。文本框样式设置。进度条样式。滑块条样式。单选框样式。滚动条样式。可自由设置对象的高度宽度大小等。自带默认参数值。 下面是demo演示&#xff1a; 项目部分代码如下所示&#xff1a; #ifnd…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...