当前位置: 首页 > 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…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

Qwen系列之Qwen3解读:最强开源模型的细节拆解

文章目录 1.1分钟快览2.模型架构2.1.Dense模型2.2.MoE模型 3.预训练阶段3.1.数据3.2.训练3.3.评估 4.后训练阶段S1: 长链思维冷启动S2: 推理强化学习S3: 思考模式融合S4: 通用强化学习 5.全家桶中的小模型训练评估评估数据集评估细节评估效果弱智评估和民间Arena 分析展望 如果…...