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

数据结构与算法之递归: LeetCode 79. 单词搜索 (Ts 版)

单词搜索

  • https://leetcode.cn/problems/word-search/description/

描述

  • 给定一个 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 更大的情况下可以更快解决问题?

Typescript 版算法实现


1 ) 方案1: 回溯

function exist(board: string[][], word: string): boolean {const h = board.length, w = board[0].length;const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];const visited = new Array(h);for (let i = 0; i < visited.length; ++i) {visited[i] = new Array(w).fill(false);}const check = (i, j, s, k) => {if (board[i][j] != s.charAt(k)) {return false;} else if (k == s.length - 1) {return true;}visited[i][j] = true;let result = false;for (const [dx, dy] of directions) {let newi = i + dx, newj = j + dy;if (newi >= 0 && newi < h && newj >= 0 && newj < w) {if (!visited[newi][newj]) {const flag = check(newi, newj, s, k + 1);if (flag) {result = true;break;}}}}visited[i][j] = false;return result;}for (let i = 0; i < h; i++) {for (let j = 0; j < w; j++) {const flag = check(i, j, word, 0);if (flag) {return true;}}}return false;
};

2 ) 方案2: 回溯优化

function exist(board: string[][], word: string): boolean {// 输入的终止条件if (board.length === 0) return falseif (word.length === 0) return true//递归函数function find(i, j, cur) {if (i >= row || i < 0) return falseif (j >= col || j < 0) return false// if()let letter = board[i][j]// 查询结束判断if (letter !== word[cur]) return false// 最后一个 也是匹配的if (cur == word.length - 1) return trueboard[i][j] = null //选择当前的字母// 进行下一步 有一个找到就算const ret = find(i + 1, j, cur + 1) ||find(i - 1, j, cur + 1) ||find(i, j + 1, cur + 1) ||find(i, j - 1, cur + 1)board[i][j] = letter //回撤return ret}//开始循环找const row = board.lengthconst col = board[0].lengthfor (let i = 0; i < row; i++) {for (let j = 0; j < col; j++) {//每一个字母都可以作为起点搜索const ret = find(i, j, 0)  //0就是当前查询的字母索引if (ret) return ret}}return false //结束的时候还没找到
};

相关文章:

数据结构与算法之递归: LeetCode 79. 单词搜索 (Ts 版)

单词搜索 https://leetcode.cn/problems/word-search/description/ 描述 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 单词必须按照字母顺序&#xff0c;通过相邻的单…...

智能系统的感知和决策

智能系统在感知和决策过程中具备的关键能力表现在智能感知/自主判定上&#xff0c;下面可以从感知的本质、自主判断的含义及其在智能系统中的作用进行深入分析。 1、智能感知&#xff1a;信息获取与理解 智能感知是指智能系统通过传感器或其他数据采集手段获取环境中的信息&…...

多线程之旅:线程安全问题

之前说到了多线程的创建和一些属性等等&#xff0c;接下来&#xff0c;就来讲讲多线程安全问题。 小编引入这段代码讲解下&#xff1a; public class Demo13 {public static int count0;public static void main(String[] args) throws InterruptedException {Thread t1new…...

用java配合redis 在springboot上实现令牌桶算法

令牌桶算法配合 Redis 在 Java 中的应用令牌桶算法是一种常用的限流算法&#xff0c;适用于控制请求的频率&#xff0c;防止系统过载。结合 Redis 使用可以实现高效的分布式限流。 一.、引入依赖首先&#xff0c;需要在 pom.xml 文件中引入 spring-boot-starter-data-re…...

科学计算库NumPy

NumPy是高性能科学计算和数据分析的基础包。 认识NumPy数据对象 n维数组对象ndarray(array) 数组是编程语言中重要且复杂的数据结构&#xff0c;它是由相同类型元素按照一定的顺序排列的集合。ndarray具有矢量算术能力和复杂的广播能力。 - 维度又称为维数&#xff0c;在数学…...

【大数据】机器学习----------强化学习机器学习阶段尾声

一、强化学习的基本概念 注&#xff1a; 圈图与折线图引用知乎博主斜杠青年 1. 任务与奖赏 任务&#xff1a;强化学习的目标是让智能体&#xff08;agent&#xff09;在一个环境&#xff08;environment&#xff09;中采取一系列行动&#xff08;actions&#xff09;以完成一个…...

Unicode不可见字符

场景复现 在访问 https://dotnet.microsoft.com/zh-cn/apps/aspnet地址时 突然出现 https://dotnet.microsoft.com/zh-cn/apps/aspnet%E2%80%8C%E2%80%8C 但是正常来看&#xff0c;这个地址后面是没有%E2%80%8C%E2%80%8C的&#xff0c;粘贴到idea里发现了url地址后面还拼接了2…...

w172二手车交易系统的设计与实现

&#x1f64a;作者简介&#xff1a;多年一线开发工作经验&#xff0c;原创团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339;赠送计算机毕业设计600个选题excel文…...

TRELLIS微软的图生3D

TRELLIS 教程目录&#xff1a; Youtube&#xff1a;https://www.youtube.com/watch?vJqFHZ-dRMhI 官网地址&#xff1a;https://trellis3d.github.io/ GitHub&#xff1a;https://github.com/Microsoft/TRELLIS 部署目录&#xff1a; 克隆项目 git clone --recurse-submodul…...

【力扣:新动计划,编程入门 —— 题解 ①】

向前看&#xff0c;总会有新的故事值得期盼 —— 25.1.21 2235. 两整数相加 给你两个整数 num1 和 num2&#xff0c;返回这两个整数的和。 示例 1&#xff1a; 输入&#xff1a;num1 12, num2 5 输出&#xff1a;17 解释&#xff1a;num1 是 12&#xff0c;num2 是 5 &#x…...

如何使用 Pytest -k 选项轻松筛选测试用例

关注开源优测不迷路 大数据测试过程、策略及挑战 测试框架原理&#xff0c;构建成功的基石 在自动化测试工作之前&#xff0c;你应该知道的10条建议 在自动化测试中&#xff0c;重要的不是工具 你是否曾不得不从成百上千个测试中费力筛选&#xff0c;只为运行几个特定的测试&am…...

C语言之小型成绩管理系统

&#x1f31f; 嗨&#xff0c;我是LucianaiB&#xff01; &#x1f30d; 总有人间一两风&#xff0c;填我十万八千梦。 &#x1f680; 路漫漫其修远兮&#xff0c;吾将上下而求索。 C语言之小型成绩管理系统 目录 设计题目设计目的设计任务描述设计要求输入和输出要求验收要…...

C++ ——— 模拟实现 vector 类

目录 vector 类的框架 无参数的构造函数 析构函数 获取有效数据个数 获取容量 重载 [] 运算符 可读可写版本 只可读版本 扩容 尾插 实现迭代器 可读可写版本 只可读版本 自定义设置size长度和内容 在任意位置插入 删除任意位置的数据 赋值重载 vector 类的框…...

SpringBoot实现轻量级动态定时任务管控及组件化

1关于动态定时任务 关于在SpringBoot中使用定时任务&#xff0c;大部分都是直接使用SpringBoot的Scheduled注解&#xff0c;如下&#xff1a; Component public class TestTask {Scheduled(cron"0/5 * * * * ? ") //每5秒执行一次public void execute(){SimpleDa…...

STM32 FreeRTOS 任务挂起和恢复---实验

实验目标 学会vTaskSuspend( )、vTaskResume( ) 任务挂起与恢复相关API函数使用&#xff1a; start_task:用来创建其他的三个任务。 task1&#xff1a;实现LED1每500ms闪烁一次。 task2&#xff1a;实现LED2每500ms闪烁一次。 task3&#xff1a;判断按键按下逻辑&#xff0c;KE…...

#漏洞挖掘# 一文了解什么是Jenkins未授权访问!!!

免责声明 本教程仅为合法的教学目的而准备&#xff0c;严禁用于任何形式的违法犯罪活动及其他商业行为&#xff0c;在使用本教程前&#xff0c;您应确保该行为符合当地的法律法规&#xff0c;继续阅读即表示您需自行承担所有操作的后果&#xff0c;如有异议&#xff0c;请立即停…...

1.21学习记录

misc 2023isctf 你说爱我尊嘟假嘟 这题有点脑洞&#xff0c;需要把你说爱我换成Ook.将尊嘟换为Ook&#xff01;假嘟换成Ook&#xff1f;&#xff08;根据语气进行猜测吧&#xff09;用在线工具解密最后用base64解密即可 2023isctf 杰伦可是流量明星 解压后是一个MP3文件&am…...

【Pandas】pandas Series groupby

Pandas2.2 Series Function application, GroupBy & window 方法描述Series.apply()用于将一个函数应用到 Series 的每个元素或整个 SeriesSeries.agg()用于对 Series 数据进行聚合操作Series.aggregate()用于对 Series 数据进行聚合操作Series.transform()用于对 Series…...

Text2SQL 智能报表方案介绍

0 背景 Text2SQL智能报表方案旨在通过自然语言处理&#xff08;NLP&#xff09;技术&#xff0c;使用户能够以自然语言的形式提出问题&#xff0c;并自动生成相应的SQL查询&#xff0c;从而获取所需的数据报表&#xff0c;用户可根据得到结果展示分析从而为结论提供支撑&#…...

51c~SLAM~合集1

我自己的原文哦~ https://blog.51cto.com/whaosoft/12327374 #GSLAM 自动驾驶相关~~~ 一个通用的SLAM架构和基准 GSLAM&#xff1a;A General SLAM Framework and Benchmark 开源代码&#xff1a;https://github.com/zdzhaoyong/GSLAM SLAM技术最近取得了许多成功&am…...

服务器安装ESXI7.0系统及通过离线包方式升级到ESXI8.0

新到了一台物理服务器需要安装系统&#xff0c;项目不急用&#xff0c;先拿来做些实验。 本次实验目标&#xff1a; 1、在物理服务器上安装ESXI7.0系统&#xff1b; 2、通过离线包升级方式将ESXI7.0升级为ESXI8.0。 实验环境准备&#xff1a; 物理服务器1台&#xff0c;型号…...

计算机网络 (52)秘钥分配

一、重要性 在计算机网络中&#xff0c;密钥分配是密钥管理中的一个核心问题。由于密码算法通常是公开的&#xff0c;因此网络的安全性主要依赖于密钥的安全保护。密钥分配的目的是确保密钥在传输过程中不被窃取或篡改&#xff0c;同时确保只有合法的用户才能获得密钥。 二、方…...

xctf-comment(Intruder,git恢复,SQL注入,Hex解码)

这题是2018年网鼎杯真题&#xff0c;考察 Burp Suite 的 Intruder 模块去找用户密码&#xff0c;使用 githacker 恢复代码&#xff08;githack不行&#xff09;&#xff0c;代码审计发现SQL二次注入&#xff0c;尝试SQL注入读取文件内容&#xff0c;读取的是/home/www/.bash_hi…...

Docker Compose创建镜像服务

什么是Docker Compose 使用Docker Compose&#xff0c;可以使用YAML配置文件&#xff08;称为Compose文件&#xff09;来配置应用程序的服务&#xff0c;然后使用Compose CLI从配置中创建并启动所有服务 。 Compose文件的默认路径是compose.yaml&#xff08;首选&#xff09;…...

kafka学习笔记5 PLAIN认证——筑梦之路

在Kafka中&#xff0c;SASL&#xff08;Simple Authentication and Security Layer&#xff09;机制包括三种常见的身份验证方式&#xff1a; SASL/PLAIN认证&#xff1a;含义是简单身份验证和授权层应用程序接口&#xff0c;PLAIN认证是其中一种最简单的用户名、密码认证方式&…...

Walrus Learn to Earn计划正式启动!探索去中心化存储的无限可能

本期 Learn to Earn 活动将带领开发者和区块链爱好者深入探索 Walrus 的技术核心与实际应用&#xff0c;解锁分布式存储的无限可能。参与者不仅能提升技能&#xff0c;还能通过完成任务赢取丰厚奖励&#xff01;&#x1f30a; 什么是 Walrus&#xff1f; 数据主权如今正成为越…...

Linux学习笔记

1、什么是Linux Linux,一般指GNU/Linux&#xff08;单独的Linux内核并不可直接使用&#xff0c;一般搭配GUN套件&#xff0c;故得此称呼&#xff09;&#xff0c;是一种免费使用和自由传播的类UNIX操作系统。它主要受到Minix和Unix思想的启发&#xff0c;是一个基于POSIX的多用…...

解锁电商设计新速度:StartAI插件制作产品图实操教程

在电商设计这片竞争激烈的战场上&#xff0c;每一位设计师都在追求高效与创意的完美融合。繁琐的背景抠图、单一的设计模板、紧迫的时间周期&#xff0c;常常让我们力不从心。但现在&#xff0c;StartAI插件的问世&#xff0c;为我们的设计之路带来了革命性的改变。下面&#x…...

AutoPrompt框架和实操:如何用AutoPrompt完成电影评论和聊天审核任务?

1. AutoPrompt框架概述 1.1 框架定义与目标 AutoPrompt是一个旨在提升和完善用户提示以适应现实世界用例的提示优化框架。该框架通过迭代生成具有挑战性的边缘案例数据集,并相应地优化提示,从而自动生成针对用户意图量身定制的高质量、详细的提示。其核心目标是利用大型语言…...

修复 Kubernetes Deployment 修改后未生效的问题

在 Kubernetes 集群中&#xff0c;当尝试修改某些 Deployment 资源&#xff08;如 calico-kube-controllers&#xff09;的 image 配置时&#xff0c;发现修改总是未生效&#xff0c;并恢复到原样。这种问题通常是因为 Deployment 资源受到其他控制器&#xff08;如 Operator&a…...

Excel 技巧17 - 如何计算倒计时,并添加该倒计时的数据条(★)

本文讲如何计算倒计时&#xff0c;并添加该倒计时的数据条。 1&#xff0c;如何计算倒计时 这里也要用公式 D3 - TODAY() 显示为下面这个样子的 然后右键该单元格&#xff0c;选 设置单元格格式 然后点 常规 这样就能显示出还书倒计时的日数了。 下拉适用到其他单元格。 2&a…...

Golang Gin系列-5:数据模型和数据库

在这篇Gin教程的博客中&#xff0c;我们将探索如何将模型和数据库与Gin框架无缝集成&#xff0c;使你能够构建健壮且可扩展的web应用程序。通过利用流行的库并遵循最佳实践&#xff0c;你将学习如何定义模型、建立数据库连接、执行CRUD操作以及确保基于gin的项目中的数据完整性…...

Android系统开发(十九):无缝拉伸的艺术——9-Patch 可绘制对象详解

引言 在移动开发中&#xff0c;背景、标题以及其他界面元素的设计质量直接影响用户体验。然而&#xff0c;如何让图片适应不同分辨率设备&#xff0c;成为开发者常常头疼的问题。这时&#xff0c;9-Patch 闪亮登场&#xff01;它不仅可以无缝拉伸&#xff0c;还能保持视觉效果…...

物联网网关Web服务器--CGI开发实例BMI计算

本例子通一个计算体重指数的程序来演示Web服务器CGI开发。 硬件环境&#xff1a;飞腾派开发板&#xff08;国产E2000处理器&#xff09; 软件环境&#xff1a;飞腾派OS&#xff08;Phytium Pi OS&#xff09; 硬件平台参考另一篇博客&#xff1a;国产化ARM平台-飞腾派开发板…...

计算机网络 (51)鉴别

前言 计算机网络鉴别是信息安全领域中的一项关键技术&#xff0c;主要用于验证用户或信息的真实性&#xff0c;以及确保信息的完整性和来源的可靠性。 一、目的与重要性 鉴别的目的是验明用户或信息的正身&#xff0c;对实体声称的身份进行唯一识别&#xff0c;以便验证其访问请…...

Mellanox ConnectX 系列网卡的双驱动架构:以太网与 InfiniBand 的协同设计

在现代数据中心和高性能计算(HPC)环境中,网络硬件的性能和功能至关重要。Mellanox ConnectX 系列网卡以其卓越的性能和多功能性而闻名,支持从传统的以太网到高性能的 InfiniBand 网络协议。这种多功能性使得 Mellanox 网卡能够满足不同应用场景的需求,从常规的数据中心网络…...

【Java】阿里环球Antom支付对接

阿里环球Antom支付对接 线上文档地址&#xff1a; GitHub&#xff1a;https://github.com/alipay/global-open-sdk-java 文档&#xff1a;https://global.alipay.com/docs/ac/ams_zh-cn/session_cashier maven&#xff1a; <!--阿里国际支付--><dependency><g…...

【vim】vim编辑器如何设置行号

vim编辑器如何设置行号 一、**临时设置行号**二、永久设置行号2.1. **用户配置文件方式&#xff08;针对当前用户&#xff09;**2.2. **全局配置文件方式&#xff08;谨慎使用&#xff0c;会影响所有用户&#xff09;** 在Vim中设置行号有以下两种常见的方法&#xff1a; 一、…...

爬虫基础之爬取某站视频

目标网址:为了1/4螺口买小米SU7&#xff0c;开了一个月&#xff0c;它值吗&#xff1f;_哔哩哔哩_bilibili 本案例所使用到的模块 requests (发送HTTP请求)subprocess(执行系统命令)re (正则表达式操作)json (处理JSON数据) 需求分析: 视频的名称 F12 打开开发者工具 or 右击…...

2024嵌入式系统的未来发展与技术洞察分享

时间如白驹过隙&#xff0c;不知不觉又是一年&#xff0c;这一年收获满满。接下来&#xff0c;将本年度对技术的感悟和洞察分析如下&#xff0c;希望对大家有所帮助。 在过去几十年里&#xff0c;嵌入式系统技术迅速发展&#xff0c;成为现代电子设备和智能硬件的核心组成部分。…...

[微服务]注册中心优化

环境隔离 企业实际开发中&#xff0c;往往会搭建多个运行环境&#xff0c;例如&#xff1a; 开发环境测试环境预发布环境生产环境 这些不同环境之间的服务和数据之间需要隔离。 还有的企业中&#xff0c;会开发多个项目&#xff0c;共享nacos集群。此时&#xff0c;这些项目…...

Leetcode 3426. Manhattan Distances of All Arrangements of Pieces

Leetcode 3426. Manhattan Distances of All Arrangements of Pieces 1. 解题思路2. 代码实现 题目链接&#xff1a;3426. Manhattan Distances of All Arrangements of Pieces 1. 解题思路 这道题很惭愧&#xff0c;一开始没有搞定&#xff0c;后来看了答案想了想&#xff…...

【重庆市乡镇界】面图层shp格式arcgis数据乡镇名称和编码wgs84坐标无偏移内容测评

标题中的“最新重庆市乡镇界面图层shp格式arcgis数据乡镇名称和编码wgs84坐标无偏移最新”指的是一个地理信息系统&#xff08;GIS&#xff09;的数据集&#xff0c;特别设计用于ArcGIS软件。这个数据集包含了重庆市所有乡镇的边界信息&#xff0c;以Shapefile&#xff08;.shp…...

基于ChatGPT的论文写作辅助工具研究

**基于ChatGPT的论文写作辅助工具研究** **摘要**&#xff1a; 随着人工智能技术的飞速发展&#xff0c;自然语言处理&#xff08;NLP&#xff09;领域取得了显著进步。ChatGPT作为OpenAI最新推出的生成式预训练Transformer模型&#xff0c;在文本生成、对话系统等方面展现出…...

定时器setTimeout和setInterval

setTimeOut()异步 setInterval()异步...

PCL 部分点云视点问题【2025最新版】

目录 一、问题概述二、解决方案1、软件实现2、代码实现三、调整之后博客长期更新,本文最近更新时间为:2025年1月18日。 一、问题概述 针对CloudCompare软件处理过的pcd格式点云,在使用PCL进行特征点提取、配准等实验中最终显示结果出现点云位置偏差较大的问题,本博客给出解…...

Cursor 与常见集成开发环境(IDE)的优势对比

Cursor与常见集成开发环境&#xff08;IDE&#xff09;的优势对比 一、AI 辅助编程能力 强大的代码生成功能&#xff1a; Cursor&#xff1a; 以其内置的强大 AI 辅助编程功能为核心优势。用户可以通过输入自然语言描述&#xff0c;快速生成各种编程语言的代码。例如&#xf…...

TDengine 做为 FLINK 数据源技术参考手册

Apache Flink 是一款由 Apache 软件基金会支持的开源分布式流批一体化处理框架&#xff0c;可用于流处理、批处理、复杂事件处理、实时数据仓库构建及为机器学习提供实时数据支持等诸多大数据处理场景。与此同时&#xff0c;Flink 拥有丰富的连接器与各类工具&#xff0c;可对接…...

不重启JVM,替换掉已经加载的类

不重启JVM&#xff0c;替换掉已经加载的类 直接操作字节码 使用ASM框架直接操作class文件&#xff0c;在类中修改代码&#xff0c;然后retransform就可以了 下边是BTrace官方提供的一个简单例子&#xff1a; package com.sun.btrace.samples;import com.sun.btrace.annotati…...

axios的使用总结

一、Axios 简介 Axios 是一个基于 Promise 的 HTTP 客户端&#xff0c;用于浏览器和 Node.js。在 Vue 项目中&#xff0c;它主要用于发送 HTTP 请求来获取数据&#xff08;如从 API 获取数据&#xff09;或者提交数据&#xff08;如用户登录、注册等表单数据&#xff09;。 二…...