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

回溯-单词搜索

news 来源：原创 2025/8/6 14:35:01

79.单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

输入：二维字符数组，给定字符串
输出：布尔值
思路：遍历字符数组，下上右左递归回溯

递归参数：当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
终止条件：
返回 false ： (1) 行或列索引越界或 (2) 当前矩阵元素与目标字符不同或 (3) 当前矩阵元素已访问过（ (3) 可合并至 (2) ）。
返回 true ： k = len(word) - 1 ，即字符串 word 已全部匹配。
递推工作：
标记当前矩阵元素：将 board[i][j] 修改为空字符‘\0’ ，代表此元素已访问过，防止之后搜索时重复访问。
搜索下一单元格：朝当前元素的上、下、左、右四个方向开启下层递归，使用或连接（代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
还原当前矩阵元素：将 board[i][j] 元素还原至初始值，即 word[k]

class Solution {public boolean exist(char[][] board, String word) {char[] words = word.toCharArray();//字符数组长度int x = board.length;int y = board[0].length;//遍历字符数组for(int i = 0; i < x; i++){for(int j = 0; j < y; j++){if(backTrack(board, words, i, j, 0)){return true;}}}return false;}public boolean backTrack(char[][] board, char[] words, int x, int y, int index){//递归结束//数组越界， 或者元素不符  if(x < 0 || y < 0 ||x >= board.length ||y >= board[0].length ||board[x][y] != words[index]){return false;}//遍历到words最后一个元素if(index == words.length - 1){return true;}//将现在的字符置为空，防止重复访问board[x][y] = '\0';//递归下上右左boolean res = backTrack(board, words, x + 1, y, index + 1) ||backTrack(board, words, x - 1, y, index + 1) || backTrack(board, words, x, y + 1, index + 1) || backTrack(board, words, x, y - 1, index + 1);//还原board[x][y] = words[index];return res;}}

相关文章：

回溯-单词搜索

79.单词搜索给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平…...

编程日记 2025/8/6 14:35:01

高级java每日一道面试题-2025年3月07日-微服务篇[Eureka篇]-Eureka Server和Eureka Client关系?

如果有遗漏,评论区告诉我进行补充面试官: Eureka Server和Eureka Client关系? 我回答: 在微服务架构中，Eureka作为Netflix开源的服务发现组件，由Eureka Server（服务端）和Eureka Client（客户端）两大部分…...

编程日记 2025/8/6 14:27:20

SpringBoot有几种获取Request对象的方法

HttpServletRequest 简称 Request，它是一个 Servlet API 提供的对象，用于获取客户端发起的 HTTP 请求信息。例如：获取请求参数、获取请求头、获取 Session 会话信息、获取请求的 IP 地址等信息。那么问题来了，在 Spring Boot 中…...

编程日记 2025/8/6 14:33:00

【Agent】Dify Docker 安装问题 INTERNAL SERVER ERROR

总结：建议大家选择稳定版本的分支，直接拉取 master 分支，可能出现一下后面更新代码导致缺失一些环境内容。我是通过 Docker 进行安装的，由于项目开发者不严谨导致，遇到一个奇怪的问题： INTERNAL SERVER E…...

编程日记 2025/7/28 20:11:59

操作系统——（处理机调度与死锁）

目录一、处理机调度 （1）层次 （2）进程调度 （3）调度算法 1.先来先服务算法（FCFS） 2.短作业优先算法（SJF） 3.高优先权算法（HPF） …...

编程日记 2025/8/6 14:28:02

MyBatis 面试专题

MyBatis 面试专题基础概念MyBatis中的工作原理MyBatis 与 Hibernate 的区别？#{} 和 ${} 的区别？MyBatis 的核心组件有哪些？ 映射与配置如何传递多个参数？ResultMap 的作用是什么？动态 SQL 常用标签有哪些？…...

编程日记 2025/8/6 14:32:35

C++实现大整数相加

力扣原题字符串相加 415. 字符串相加 - 力扣（LeetCode） 大整数意味着无法用基本数据类型装下，只能用字符串装下，然后手工模拟计算过程从两个字符串的最后一位开始两两相加，记录进位，每次均有sumabsum&…...

编程日记 2025/8/6 14:29:37

Flutter 快速接入Fair

少点废话 1.了解Fair Fair，由58同城开源提供，目的是flutter项目上架后动态更新代码， 首先了解一个概念，热更新是flutter打包APK后会讲所有的dart代码生成一个so文件，手机通过读取并执行so文件；基于此&am…...

编程日记 2025/8/6 5:11:01

【深度学习新浪潮】AI ISP技术与手机厂商演进历史

本文是关于AI ISP（人工智能图像信号处理器）的技术解析、与传统ISP（图像信号处理器）的区别、近三年研究进展，以及各大手机厂商在该领域演进历史的详细报告。本报告综合多个权威来源的信息，力求全面、深入地呈现相关技术发展脉络与行业动态。第一部分：AI ISP的定义及与传…...

编程日记 2025/8/6 14:31:01

用逻辑分析仪分析Usart波形

USART的波形抓取最简单，帧头帧尾只需要电平上升下降沿就可以了，不需要自己定义，也没有ID位，逻辑分析仪可以直接抓取发送的数据： 口配置：9600bps，8数据位，无校验，1个停止位…...

编程日记 2025/8/5 17:19:38

常⻅CMS漏洞 -DeDeCMS 获取webshell

DedeCMS是织梦团队开发PHP ⽹站管理系统，它以简单、易⽤、⾼效为特⾊，组建出各种各样各具特⾊的⽹站姿势⼀：通过⽂件管理器上传WebShell 1.访问⽬标靶场dedecms 后台可以直接上传任意⽂件 2.上传木马文件 3.蚁剑连接姿势⼆：…...

编程日记 2025/8/6 14:30:03

基于STC89C51的太阳自动跟踪系统的设计与实现—单片机控制步进电机实现太阳跟踪控制(仿真+程序+原理图+PCB+文档)

摘要随着我国经济的飞速发展，促使各种能源使用入不敷出，尤其是最主要的能源，煤炭石油资源不断消耗与短缺，因此人类寻找其他替代能源的脚步正在加快。而太阳能则具有无污染﹑可再生﹑储量大等优点，且分布范围广&…...

编程日记 2025/8/6 8:44:02

JAVA_数据结构_栈和队列

1.栈（Stack） 1.1概念栈是一种特殊的线性表，它只允许一端进行增删查改操作，它的头称为栈顶，进行压栈和出栈的操作，则另一端称为栈底，并且它遵循着先进后出的操作。压栈：也可称为进…...

编程日记 2025/8/6 14:30:02

独立组网和非独立组网

独立组网（SA） vs. 非独立组网（NSA） 5G组网方式主要分为独立组网（SA, Standalone） 和非独立组网（NSA, Non-Standalone），两者在网络架构、核心网、应用场景等方面有所不…...

编程日记 2025/7/28 19:43:24

HR人员和组织信息同步AD域服务器实战方法JAVA

HR人员和组织信息同步AD域服务器前期准备AD域基础知识整理HR同步AD的逻辑代码结构配置文件设置启动类HR组织的BeanHR人员Bean获取HR人员和组织信息的类AD中处理组织和人员的类日志配置 POM.xml文件生成EXE文件服务器定时任务异常问题注意事项前期准备 1、开发语言&#xff1…...

编程日记 2025/8/6 14:25:10

【云上CPU玩转AIGC】——腾讯云高性能应用服务HAI已支持DeepSeek-R1模型预装环境和CPU算力

🎼个人主页：【Y小夜】 😎作者简介：一位双非学校的大三学生，编程爱好者， 专注于基础和实战分享，欢迎私信咨询！ 🎆入门专栏：🎇【MySQL&#xff0…...

编程日记 2025/8/2 11:16:48

【测试开发】OKR 网页管理端自动化测试报告

【测试报告】OKR 管理端项目名称版本号测试负责人测试完成日期联系方式OKR 管理端4.0马铭胜2025-03-2115362558972 1、项目背景 1.1 OKR 用户端在如今这个快节奏的时代中，个人和组织的成长往往依赖于清晰、明确且意义深远的目标。然而，如何设定并持…...

编程日记 2025/8/6 14:28:01

go语言中空结构体

空结构体(struct{}) 普通理解在结构体中，可以包裹一系列与对象相关的属性，但若该对象没有属性呢？那它就是一个空结构体。空结构体，和正常的结构体一样，可以接收方法函数。 type Lamp struct{}func (l Lamp) On()…...

编程日记 2025/8/6 14:29:37

如何缓解大语言模型推理中的“幻觉”（Hallucination）？

目录如何缓解大语言模型推理中的“幻觉”（Hallucination）？ 1. 什么是大语言模型的“幻觉”（Hallucination）？ 幻觉的常见类型 2. 如何缓解大模型的幻觉问题？ 方法 1：使用知识检索…...

编程日记 2025/8/6 7:42:55

优选算法系列（3.二分查找）

目录一.二分查找（easy） 题目链接：704. 二分查找 - 力扣（LeetCode） 解法： 代码： 二.在排序数组中查找元素的第⼀个和最后⼀个位置（medium） 题目链接：34.…...

编程日记 2025/8/4 5:02:38

【论文阅读】Contrastive Clustering Learning for Multi-Behavior Recommendation

论文地址：Contrastive Clustering Learning for Multi-Behavior Recommendation | ACM Transactions on Information Systems 摘要近年来，多行为推荐模型取得了显著成功。然而，许多模型未充分考虑不同行为之间的共性与差异性，以…...

编程日记 2025/8/6 10:57:00

细胞计数专题 | 高效 + 精准！点成LUNA-III™细胞计数仪解锁活细胞检测与浓度分析新高度

1 引言在生物医学研究中，准确的细胞计数至关重要，它影响着细胞治疗、疾病诊断、组织再生和生物测定等应用领域。传统的手动计数方法既耗时又容易产生偏差。像点成LUNA-III™自动细胞计数仪这样的自动化系统，为提高计数的准确性、可重复性和…...

编程日记 2025/8/4 20:51:49

糊涂人寄信——递推

思路分析：当有n封信，n个信封时。第k封信没有装在第k个信封里（k从1~n），就算所有的信封都装错了。我们可以得知的是，当有1封信,时，装错类别数为0。当有两封信时，装错类别为1。当有三…...

编程日记 2025/8/1 12:14:54

深入Python C API：掌握常用函数与实战技巧

深入Python C API：掌握常用函数与实战技巧 Python的灵活性和易用性使其成为广泛应用的编程语言，但在某些场景下（如高性能计算、与C/C代码交互），直接使用C语言扩展Python的能力变得尤为重要。Python C API（…...

编程日记 2025/7/30 17:10:08

第16章：基于CNN和Transformer对心脏左心室的实验分析及改进策略

目录 1. 项目需求 2. 网络选择 2.1 UNet模块 2.2 TransUnet 2.2.1 SE模块 2.2.2 CBAM 2.3 关键代码 3 对比试验 3.1 unet 3.2 transformerSE 3.3 transformerCBAM 4. 结果分析 5. 推理 6. 下载 1. 项目需求本文需要做的工作是基于CNN和Transformer的心脏左心室…...

编程日记 2025/7/31 12:54:17

Word中公式自动标号带章节编号

（1）插入一行三列的表格，设置宽度分别为0.5，13.39和1.5，设置纵向居中，中间列居中对齐，最右侧列靠右对齐，设置段落如下 （2）插入域代码【Word】利用域代码快速实…...

编程日记 2025/8/4 3:53:32

AI风向标《AI与视频制作全攻略：从入门到精通实战课程》

课程信息 AI风向标《AI与视频制作全攻略：从入门到精通实战课程》,夸克网盘和百度网盘课程。课程介绍《AI与视频制作全攻略：从入门到精通实战课程》是一套全面融合AI技术与视频制作的实战课程，旨在帮助创作者从基础软件使用到高级视频剪辑…...

编程日记 2025/8/2 13:41:24

el-table折叠懒加载支持排序

el-table折叠懒加载支持排序因为el-table懒加载的子节点是通过缓存实现的，如果想在展开的情况下直接刷新对应子节点数据，要操作el-table组件自身数据，否则不会更新以排序功能为例 maps: new Map() //用于存储子节点懒加载的数据// 加载子…...

编程日记 2025/7/30 7:09:49

Kotlin v2.1.20 发布，标准库又有哪些变化？

大家吼哇！就在三小时前，Kotlin v2.1.20 发布了，更新的内容也已经在官网上更新：What’s new in Kotlin 2.1.20 。我粗略地看了一下，下面为大家选出一些我比较感兴趣、且你可能也会感兴趣的内容。注意！这里…...

编程日记 2025/8/2 13:41:55

AI智能问答“胡说八道“-RAG探索之路

AI智能问答"胡说八道"-RAG探索之路背景信息RAGRAG技术的知识难题分块矛盾知识缺失相互冲突 RAG知识优化实践分块优化缺失优化冲突优化未来展望背景信息你有没有遇到过这样的场景？当你向智能助手提问：“某科技公司为何突然更换高层领导&am…...

编程日记 2025/8/5 7:32:06

【yolo】YOLO训练参数输入之模型输入尺寸

模型输入尺寸是YOLO训练和推理过程中非常重要的参数之一。YOLO要求输入图像的尺寸是固定的，通常为正方形（如416416、640640等）。这个尺寸直接影响模型的性能和速度。以下是对模型输入尺寸的详细介绍： 1. 模型输入尺寸的作用统一…...

编程日记 2025/8/5 4:39:59

[原创](Modern C++)现代C++的关键性概念: 如何声明一个返回数组指针的函数?

[作者] 常用网名: 猪头三出生日期: 1981.XX.XX 企鹅交流: 643439947 个人网站: 80x86汇编小站编程生涯: 2001年~至今[共24年] 职业生涯: 22年开发语言: C/C、80x86ASM、Object Pascal、Objective-C、C#、R、Python、PHP、Perl、开发工具: Visual Studio、Delphi、XCode、C …...

编程日记 2025/8/6 9:12:33

1204. 【高精度练习】密码

文章目录题目描述输入输出样例输入样例输出数据范围限制CAC代码题目描述人们在做一个破译密码游戏： 有两支密码棒分别是红色和蓝色，把红色密码棒上的数字减去蓝色密码棒上的数字，就是开启密码锁的密码。现已知密码棒上的数字位数不超过…...

编程日记 2025/8/5 15:14:29

DigitalFoto公司如何用日事清流程管理工具实现任务优先级与状态可视化？

一、业务介绍在DigitalFoto，设计和制造先进的摄影器材，如稳定器、灯光设备和支架，是日常工作的核心。公司的业务模式包括为其他品牌设计和制造定制产品，无论是作为OEM还是ODM。这样的多样化业务需求推动了公司在产品开发上必须非…...

编程日记 2025/8/1 19:25:55

解锁C++编程能力：基础语法解析

C入门基础一、C的第一个程序二、命名空间三、C输入&输出四、缺省参数/默认参数五、函数重载六、引用1.引用的特性2.引用的使用引用做返回值场景 3.const引用只有指针和引用涉及权限放大、缩小的问题，普通变量没有 4.指针和引用的关系七、inline八、nullptr 一…...

编程日记 2025/8/3 23:00:04

【Leetcode 每日一题】2680. 最大或值

问题背景给你一个下标从 0 0 0 开始长度为 n n n 的整数数组 n u m s nums nums 和一个整数 k k k。每一次操作中，你可以选择一个数并将它乘 2 2 2。你最多可以进行 k k k 次操作，请你返回 n u m s [ 0 ] ∣ n u m s [ 1 ] ∣ . . . ∣ n u m …...

编程日记 2025/7/31 6:33:00

YOLO魔改之SAM空间注意力模块

基于SAM注意力的YOLOv7改进算法详解（可用于工业检测方案）一、应用场景说明本改进算法适用于以下工业检测场景：复杂背景下的微小目标检测（电子元件缺陷、PCB板焊点）密集目标重叠检测（传送带上的包裹分拣、人群计数）动态环境目标追踪（无人机巡检、自动驾…...

编程日记 2025/8/5 15:19:45

基于 TRIZ 理论的筏式养殖吊笼清洗装备设计研究

基于 TRIZ 理论的筏式养殖吊笼清洗装备设计研究一、引言筏式养殖在水产养殖业中占据重要地位，吊笼作为养殖贝类、藻类等生物的关键器具，其清洁程度直接影响养殖生物的健康与产量。传统的吊笼清洗方式多依赖人工，效率低下、劳动强度大且清洗…...

编程日记 2025/8/4 23:27:01

Day11 动态规划入门

动态规划就是 : 给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后把子问题的答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法. 记忆化搜索暴力dfs 记录答案动态规划入门思…...

编程日记 2025/8/4 1:19:50

配置阿里云yum源

配置阿里云yum源修改默认的yum仓库，把原有的移动到创建的目录里（踢出国外的yum源） # 切换到/ect/yum.repos.d/目录下 cd /etc/yum.repos.d/ # 新建repo目录 mkdir repo # 把原有的移动到创建的目录里 mv ./*.repo ./repo/配置yum源 # 找到…...

编程日记 2025/8/2 13:41:55

在Linux系统安装Ollama两种方法：自动安装和手动安装，并配置自启动服务

目录一、命令自动安装‌ （一）使用命令行安装 （二）配置环境变量 （三）重新加载systemd配置并重启服务 ‌二、手动安装‌ （一）下载本地文件 （二）解压并安…...

编程日记 2025/7/26 4:12:52

Python Django入门(创建应用程序)

在本章中，你将学习如何使用 Django（http://djangoproject.com/ ）来开发一个名为“学习笔记”（Learning Log）的项目，这是一个在线日志系统，让你能够记录所学习的有关特定主题的知识。我们将为这…...

编程日记 2025/7/31 9:31:31

HCIP-2 RSTP快速生成树

HCIP-2 RSTP快速生成树 STP的不足： 1.STP的端口角色过于简单不丰富，部署时不能很好的应用与较为复杂的网络环境中。 2.STP的迁移状态过于冗长，侦听、学习、阻塞状态下都是不转发业务流量。 3.STP的算法较为繁琐。 TCN TCA TC。 4.STP被动…...

编程日记 2025/8/3 12:59:02

软考-软件设计师-计算机网络

一、七层模型中继器：信号会随着距离的增加而逐渐衰减，中继器可以接受一端的信息再将其原封不动的发给另一端，起到延长传输距离的作用； 集线器：多端口的中继器，所有端口公用一个冲突域； 网桥&…...

编程日记 2025/8/3 4:59:48

夸克网盘任务脚本——进阶自动版

脚本是用于自动管理和更新夸克云盘（Quark Cloud Drive）上的文件和目录的Python脚本。其主要功能包括自动下载、更新、重命名、删除文件和文件夹，以及处理和发送通知,可以在特定的时间间隔内运行，根据配置文件进行操作。主要功能 1. Quark 类： __init__：初始化类，设置…...

编程日记 2025/7/30 16:16:12

squirrel语言全面介绍

Squirrel 是一种较新的程序设计语言，由意大利人 Alberto Demichelis 开发，其设计目标是成为一个强大的脚本工具，适用于游戏等对大小、内存带宽和实时性有要求的应用程序。以下是对 Squirrel 语言的全面介绍： 语言特性动态类型&a…...

编程日记 2025/8/4 0:11:10

北京南文观点：品牌如何抢占AI 认知的 “黄金节点“

在算法主导的信息洪流中，品牌正在经历一场隐蔽的认知权争夺战，当用户向ChatGPT咨询"哪家新能源车企技术最可靠"时，AI调取的知识图谱数据源将直接决定品牌认知排序。南文乐园科技文化（北京）有限公司&#xff…...

编程日记 2025/7/30 14:56:06

使用Python在Word中创建、读取和删除列表 - 详解

目录工具与设置 Python在Word中创建列表使用默认样式创建有序（编号）列表使用默认样式创建无序（项目符号）列表创建多级列表使用自定义样式创建列表 Python读取Word中的列表 Python从Word中删除列表在Word中&#xff…...

编程日记 2025/8/3 1:04:13

分布式中间件：RabbitMQ确认消费机制

分布式中间件：RabbitMQ确认消费机制在分布式系统中，消息队列是实现异步通信和系统解耦的重要组件。RabbitMQ 作为一款功能强大的消息队列中间件，提供了丰富的特性来保证消息的可靠传输和消费。其中，确认消费机制是确保消息被正确…...

编程日记 2025/8/4 18:52:26

Redis的大Key问题如何解决?

大家好，我是锋哥。今天分享关于【Redis的大Key问题如何解决?】面试题。希望对大家有帮助； Redis的大Key问题如何解决? 1000道互联网大厂Java工程师精选面试题-Java资源分享网 Redis的大Key问题指的是存储在Redis中的某些键（Key&#xf…...

编程日记 2025/8/1 13:37:37