【Leetcode 每日一题】3291. 形成目标字符串需要的最少字符串数 I
问题背景
给你一个字符串数组 w o r d s words words 和一个字符串 t a r g e t target target。
如果字符串 x x x 是 w o r d s words words 中 任意 字符串的 前缀(字符串的前缀是从字符串的开头开始并延伸到其中任意点的子串),则认为 x x x 是一个 有效 字符串。
现计划通过 连接 有效字符串形成 t a r g e t target target,请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 t a r g e t target target,则返回 − 1 -1 −1。
数据约束
- 1 ≤ w o r d s . l e n g t h ≤ 100 1 \le words.length \le 100 1≤words.length≤100
- 1 ≤ w o r d s [ i ] . l e n g t h ≤ 5 × 1 0 3 1 \le words[i].length \le 5 \times 10 ^ 3 1≤words[i].length≤5×103
- s u m ( w o r d s [ i ] . l e n g t h ) ≤ 1 0 5 sum(words[i].length) \le 10 ^ 5 sum(words[i].length)≤105
- w o r d s [ i ] words[i] words[i] 只包含小写英文字母
- 1 ≤ t a r g e t . l e n g t h ≤ 5 × 1 0 3 1 \le target.length \le 5 \times 10 ^ 3 1≤target.length≤5×103
- t a r g e t target target 只包含小写英文字母
解题过程
周赛第三题的水准,数据范围允许暴力解,似乎可以用前缀树搭配嵌套循环解决。遗憾的是我目前只会写前缀树,还不会用前缀树来解决问题。
既然要学,那就学习一下一般情形化的做法。这题可以看作将目标分割成几个部分,每个部分都是给定的数组中字符串的前缀。
要求选用的字符串尽可能少,就要每次覆盖的范围尽可能大,这就可以参考 跳跃游戏 II 和 灌溉花园的最少水龙头数目。没有保证一定能实现目标,要单独处理。
分割的部分,需要用到 扩展 KMP 算法,也叫字符串的 Z 函数,它的作用是求出一个字符串中各个后缀与它本身的最长公共前缀的长度。这个东西今天是第一次见,不要求马上能学会,先见识一下。
还有使用字符串哈希和 AC 自动机的做法,因为相应的算法还没有掌握,先不作要求,可以暂时把重点放在吃透造桥问题的贪心做法上。
具体实现
class Solution {public int minValidStrings(String[] words, String target) {int n = target.length();int[] maxJumps = new int[n];for(String word : words) {// 把目标拼到这个单词的后面,就可以求出 Z 函数来辅助计算每个字符串可取的最大前缀了// 加一个特殊字符,防止下标越界int[] z = calcZ(word + "#" + target);int m = word.length() + 1; // 这里额外加的长度,是用来修正特殊字符的// 求出目标每个位置上能够匹配到的最大前缀长度for(int i = 0; i < n; i ++) {maxJumps[i] = Math.max(maxJumps[i], z[m + i]);}}return jump(maxJumps);}// Z 函数private int[] calcZ(String s) {char[] chS = s.toCharArray();int n = chS.length;int[] z = new int[n];int left = 0, right = 0;for(int i = 1; i < n; i++) {if(i <= right) {z[i] = Math.min(z[i - left], right - i + 1);}while(i + z[i] < n && chS[z[i]] == chS[i + z[i]]) {left = i;right = i + z[i];z[i]++;}}return z;}// 造桥问题的解,参见 Leetcode 45.跳跃游戏 II 和 Leetcode 1326.灌溉花园的最少水龙头数目private int jump(int[] maxJumps) {int res = 0;int curEnd = 0;int nextEnd = 0;for(int i = 0; i < maxJumps.length; i++) {nextEnd = Math.max(nextEnd, i + maxJumps[i]);if(i == curEnd) {if(i == nextEnd) {return -1;}curEnd = nextEnd;res++;}}return res;}
}
相关文章:
【Leetcode 每日一题】3291. 形成目标字符串需要的最少字符串数 I
问题背景 给你一个字符串数组 w o r d s words words 和一个字符串 t a r g e t target target。 如果字符串 x x x 是 w o r d s words words 中 任意 字符串的 前缀(字符串的前缀是从字符串的开头开始并延伸到其中任意点的子串),则认为…...
Windows聚焦壁纸代理不更新——解除UWP应用回环限制
开代理后经常出现Microsoft store打不开,聚焦壁纸不更新的情况,因为UWP应用默认禁止回环地址,导致开了代理以后不仅用不了代理上网,还把自己的本来的通信堵死了 打开CMD输入 FOR /F "tokens11 delims\" %p IN (REG QUER…...
电脑开机提示error loading operating system怎么修复?
前一天电脑还能正常运行,但今天启动时却显示“Error loading operating system”(加载操作系统错误)。我已经仔细检查了硬盘、接线、内存、CPU和电源,确认这些硬件都没有问题。硬盘在其他电脑上可以正常使用,说明不是硬…...
javaFX.(蜜雪冰城点餐小程序)MySQL数据库
学习Java只有3个月,不喜勿喷 该小程序是用的MySQL数据库,编辑软件用的equals,为什么不用idea有提示因为主打一个纯手打 要源码私信 目录 javafx.小程序(蜜雪冰城点餐系统)简介 主体思路 思路讲解 用户登录 用户注册 忘记…...
Unity Apple Vision Pro 开发教程:物体识别跟踪
Spatial XR 开发者社区官网:SpatialXR 社区 开发流程与原理:Apple Vision Pro 物体识别跟踪原理与开发流程【Unity Apple Vision Pro 开发系列教程】 PolySpatial 物体跟踪官方样例讲解:Unity Apple Vision Pro 开发教程:物体识别…...
nano编辑器的使用
nano 是一个非常简单易用的命令行文本编辑器,它常用于在 Linux 或类 Unix 系统中快速编辑文件,特别适用于需要修改配置文件或快速编辑文本的场景。以下是一些常见的 nano 使用技巧和基本操作。 1. 打开文件 要使用 nano 编辑文件,打开终端并…...
框架问题学习
1、gin 1.1、gin框架路由是怎么处理的 在 Gin 中,路由是通过 gin.Default() 或 gin.New() 创建的 *gin.Engine 对象来管理的。gin.Default() 是 gin.New() 的一个封装,它在创建路由对象时会自动添加一个默认的中间件(如日志记录、恢复中间件…...
前端:纯前端快速实现html导出word和pdf
实现html导出word,需要使用两个库。 html-docx-js和file-saver 导出word的js方法 > npm install html-docx-js >npm install file-saver js引入 import FileSaver from “file-saver”; import htmlDocx from “html-docx-js/dist/html-docx”; /**导出…...
三相异步电动机如何调试?
在现代工业中,三相异步电动机因其结构简单、运行可靠和适应性强而被广泛应用。然而,正确的调试过程是确保电动机高效运行和延长其使用寿命的关键。 一、调试前的准备工作 在开始调试之前,必须进行充分的准备工作,以确保调试顺利…...
四川托普信息技术职业学院教案1
四川托普信息技术职业学院教案 【计科系】 周次 第 1周,第1次课 备 注 章节名称 第1章 XML语言简介 引言 1.1 HTML与标记语言 1.2 XML的来源 1.3 XML的制定目标 1.4 XML概述 1.5 有了HTML了,为什么还要发展XML 1.5.1 HTML的缺点 1.5.2 XML的特点 1.6 X…...
JS数组方法汇总
Array.from //将可迭代对象或字符串转换为数组 console.log(Array.from(1234)); //[ 1, 2, 3, 4 ]Array.isArray //判断是否是数组 Array.isArray([1])//trueArray.concat //用于合并两个或多个数组。此方法不会更改现有数组,而是返回一个新数组 let arr [1,2,3]…...
安装milvus以及向量库增删改操作
首先电脑已经安装了docker windows电脑可下载yml文件 https://github.com/milvus-io/milvus/releases/download/v2.4.6/milvus-standalone-docker-compose.yml 创建milvus文件夹,并在这个目录下创建五个文件夹:conf、db、logs、pic、volumes、wal 然后…...
基于Spring Boot的找律师系统
一、系统背景与意义 在现代社会,法律服务的需求日益增长,但传统寻找律师的方式往往存在信息不透明、选择困难等问题。基于Spring Boot的找律师系统旨在解决这些问题,通过线上平台,用户可以轻松搜索、比较和选择合适的律师&#x…...
Pytorch | 利用NI-FGSM针对CIFAR10上的ResNet分类器进行对抗攻击
Pytorch | 利用NI-FGSM针对CIFAR10上的ResNet分类器进行对抗攻击 CIFAR数据集NI-FGSM介绍背景算法原理 NI-FGSM代码实现NI-FGSM算法实现攻击效果 代码汇总nifgsm.pytrain.pyadvtest.py 之前已经针对CIFAR10训练了多种分类器: Pytorch | 从零构建AlexNet对CIFAR10进行…...
深度学习实战车辆目标跟踪【bytetrack/deepsort】
本文采用YOLOv8作为核心算法框架,结合PyQt5构建用户界面,使用Python3进行开发。YOLOv8以其高效的实时检测能力,在多个目标检测任务中展现出卓越性能。本研究针对车辆目标数据集进行训练和优化,该数据集包含丰富的车辆目标图像样本…...
【C复习】模拟题题库*3总结
1.c语言中要求对变量作强制定义的主要理由是便于确定类型和分配空间 2.结构化程序由三中基本结构组成,三中基本结构组成的算法可以完成任何复杂的任务 3.数组名是一个不可变的常量 4.下列选项中,合法的C语言关键字是()。 …...
【数据分析】层次贝叶斯
文章目录 一、 贝叶斯推理二、 层次贝叶斯模型三、 层次贝叶斯的特点四、 数学表述五、推断方法六、应用领域 层次贝叶斯(Hierarchical Bayesian)方法是一种基于贝叶斯推理的统计模型,用于处理具有多个层次结构的数据模型。 它允许我们在同一…...
Layui table不使用url属性结合laypage组件实现动态分页
从后台一次性获取所有数据赋值给 Layui table 组件的 data 属性,若数据量大时,很可能会超出浏览器字符串最大长度,导致渲染数据失败。Layui table 结合 laypage 组件实现动态分页可解决此问题。 HTML增加分页组件标签 在table后增加一个用于…...
【蓝桥杯】43688-《Excel地址问题》
Excel地址问题 题目描述 Excel 单元格的地址表示很有趣,它可以使用字母来表示列号。比如, A 表示第 1 列, B 表示第 2 列, … Z 表示第 26 列, AA 表示第 27 列, AB 表示第 28 列, … BA 表示…...
【bodgeito】攻防实战记录
也许有一天我们再相逢,睁开眼睛看清楚,我才是英雄。 进入网站整体浏览网页 点击页面评分进入关卡 一般搭建之后这里都是红色的,黄色是代表接近,绿色代表过关 首先来到搜索处本着见框就插的原则 构造payload输入 <script>…...
倒反天罡了!Cursor自研模型反超Opus 4.6!价格脚踝斩,氛围编程沸腾了
因公众号更改推送规则,请点“在看”并加“星标”第一时间获取精彩技术分享点击关注#互联网架构师公众号,领取架构师全套资料 都在这里0、2T架构师学习资料干货分上一篇:2T架构师学习资料干货分享大家好,我是互联网架构师ÿ…...
数据库表的性能优化过程
问题背景做一个数据库表查看、标注与分析的工具软件。是数据库中表的信息(information_schema.tables);是的数据字典文档,存储在本地文件中;是对的额外标注信息,存储在另一个数据库中。每一条,最…...
【FMCW雷达】频率调制连续波FMCW雷达系统(从波形生成到利用小胞平均常误报率CA-CFAR进行目标检测)【含Matlab源码 15242期】含报告
💥💥💥💥💥💥💥💥💞💞💞💞💞💞💞💞💞Matlab武动乾坤博客之家💞…...
零基础入门Python爬虫:借助快马AI生成你的第一个可运行爬虫脚本
今天想和大家分享一下我作为Python爬虫新手的学习经历。刚开始接触爬虫时,面对各种库和概念真的有点懵,直到发现了InsCode(快马)平台,它让我用自然语言描述需求就能生成可运行的代码,大大降低了入门门槛。 爬虫的基本原理 爬虫就像…...
微服务架构的陷阱:我们是如何从拆分成“微”麻烦的
对于软件测试从业者而言,微服务架构的兴起既带来了前所未有的挑战,也揭示了隐藏在水面之下的诸多陷阱。从单体应用向微服务转型,初衷是为了提升系统的灵活性、可维护性和团队的交付效率。然而,在实践中,许多团队却发现…...
Conda环境回滚实战:当安装新包搞崩base环境时如何一键恢复
Conda环境回滚实战:当安装新包搞崩base环境时如何一键恢复 在Python开发中,conda作为包管理和环境管理的利器,几乎成为数据科学家的标配工具。但越是频繁使用conda,越容易遇到一个令人头疼的问题——在base环境中安装新包后&#…...
H3C IRF 四台交换机堆叠实战:环型拓扑配置详解
1. 四台H3C交换机IRF堆叠入门指南 第一次接触H3C交换机的IRF堆叠功能时,我完全被它的强大所震撼。简单来说,IRF(Intelligent Resilient Framework)技术可以把多台物理交换机虚拟成一台逻辑设备,不仅简化管理ÿ…...
APDS9960手势传感器驱动开发与嵌入式实战
1. APDS9960手势传感器库技术解析与嵌入式工程实践APDS9960是一款由Broadcom(原Avago)推出的集成环境光、颜色、接近度及手势识别功能的多模态光学传感器芯片。其核心价值在于将传统分立式光感方案(如独立ALSProximityGesture模块)…...
uboot移植实战:DDR初始化参数优化与调试指南
1. 理解DDR初始化在uboot移植中的重要性 第一次接触uboot移植时,我完全不明白为什么DDR初始化这么麻烦。直到有一次,我把开发板直接烧成砖头,才真正意识到这个环节有多关键。简单来说,DDR初始化就像是给电脑装内存条,但…...
HunyuanVideo-Foley 企业级架构设计:基于Agent的分布式音效生成调度系统
HunyuanVideo-Foley 企业级架构设计:基于Agent的分布式音效生成调度系统 1. 引言:音效生成的企业级挑战 想象一下这样的场景:一家大型视频平台每天需要为上万条视频自动生成匹配的音效。传统单机方案面临三大难题:生成速度跟不上…...
