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

【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 1words.length100
  • 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 1words[i].length5×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 1target.length5×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 中 任意 字符串的 前缀&#xff08;字符串的前缀是从字符串的开头开始并延伸到其中任意点的子串&#xff09;&#xff0c;则认为…...

Windows聚焦壁纸代理不更新——解除UWP应用回环限制

开代理后经常出现Microsoft store打不开&#xff0c;聚焦壁纸不更新的情况&#xff0c;因为UWP应用默认禁止回环地址&#xff0c;导致开了代理以后不仅用不了代理上网&#xff0c;还把自己的本来的通信堵死了 打开CMD输入 FOR /F "tokens11 delims\" %p IN (REG QUER…...

电脑开机提示error loading operating system怎么修复?

前一天电脑还能正常运行&#xff0c;但今天启动时却显示“Error loading operating system”&#xff08;加载操作系统错误&#xff09;。我已经仔细检查了硬盘、接线、内存、CPU和电源&#xff0c;确认这些硬件都没有问题。硬盘在其他电脑上可以正常使用&#xff0c;说明不是硬…...

javaFX.(蜜雪冰城点餐小程序)MySQL数据库

学习Java只有3个月&#xff0c;不喜勿喷 该小程序是用的MySQL数据库&#xff0c;编辑软件用的equals,为什么不用idea有提示因为主打一个纯手打 要源码私信 目录 javafx.小程序&#xff08;蜜雪冰城点餐系统&#xff09;简介 主体思路 思路讲解 用户登录 用户注册 忘记…...

Unity Apple Vision Pro 开发教程:物体识别跟踪

Spatial XR 开发者社区官网&#xff1a;SpatialXR 社区 开发流程与原理&#xff1a;Apple Vision Pro 物体识别跟踪原理与开发流程【Unity Apple Vision Pro 开发系列教程】 PolySpatial 物体跟踪官方样例讲解&#xff1a;Unity Apple Vision Pro 开发教程&#xff1a;物体识别…...

nano编辑器的使用

nano 是一个非常简单易用的命令行文本编辑器&#xff0c;它常用于在 Linux 或类 Unix 系统中快速编辑文件&#xff0c;特别适用于需要修改配置文件或快速编辑文本的场景。以下是一些常见的 nano 使用技巧和基本操作。 1. 打开文件 要使用 nano 编辑文件&#xff0c;打开终端并…...

框架问题学习

1、gin 1.1、gin框架路由是怎么处理的 在 Gin 中&#xff0c;路由是通过 gin.Default() 或 gin.New() 创建的 *gin.Engine 对象来管理的。gin.Default() 是 gin.New() 的一个封装&#xff0c;它在创建路由对象时会自动添加一个默认的中间件&#xff08;如日志记录、恢复中间件…...

前端:纯前端快速实现html导出word和pdf

实现html导出word&#xff0c;需要使用两个库。 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”; /**导出…...

三相异步电动机如何调试?

在现代工业中&#xff0c;三相异步电动机因其结构简单、运行可靠和适应性强而被广泛应用。然而&#xff0c;正确的调试过程是确保电动机高效运行和延长其使用寿命的关键。 一、调试前的准备工作 在开始调试之前&#xff0c;必须进行充分的准备工作&#xff0c;以确保调试顺利…...

四川托普信息技术职业学院教案1

四川托普信息技术职业学院教案 【计科系】 周次 第 1周&#xff0c;第1次课 备 注 章节名称 第1章 XML语言简介 引言 1.1 HTML与标记语言 1.2 XML的来源 1.3 XML的制定目标 1.4 XML概述 1.5 有了HTML了&#xff0c;为什么还要发展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 //用于合并两个或多个数组。此方法不会更改现有数组&#xff0c;而是返回一个新数组 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文件夹&#xff0c;并在这个目录下创建五个文件夹&#xff1a;conf、db、logs、pic、volumes、wal 然后…...

基于Spring Boot的找律师系统

一、系统背景与意义 在现代社会&#xff0c;法律服务的需求日益增长&#xff0c;但传统寻找律师的方式往往存在信息不透明、选择困难等问题。基于Spring Boot的找律师系统旨在解决这些问题&#xff0c;通过线上平台&#xff0c;用户可以轻松搜索、比较和选择合适的律师&#x…...

Pytorch | 利用NI-FGSM针对CIFAR10上的ResNet分类器进行对抗攻击

Pytorch | 利用NI-FGSM针对CIFAR10上的ResNet分类器进行对抗攻击 CIFAR数据集NI-FGSM介绍背景算法原理 NI-FGSM代码实现NI-FGSM算法实现攻击效果 代码汇总nifgsm.pytrain.pyadvtest.py 之前已经针对CIFAR10训练了多种分类器&#xff1a; Pytorch | 从零构建AlexNet对CIFAR10进行…...

深度学习实战车辆目标跟踪【bytetrack/deepsort】

本文采用YOLOv8作为核心算法框架&#xff0c;结合PyQt5构建用户界面&#xff0c;使用Python3进行开发。YOLOv8以其高效的实时检测能力&#xff0c;在多个目标检测任务中展现出卓越性能。本研究针对车辆目标数据集进行训练和优化&#xff0c;该数据集包含丰富的车辆目标图像样本…...

【C复习】模拟题题库*3总结

1.c语言中要求对变量作强制定义的主要理由是便于确定类型和分配空间 2.结构化程序由三中基本结构组成&#xff0c;三中基本结构组成的算法可以完成任何复杂的任务 3.数组名是一个不可变的常量 4.下列选项中&#xff0c;合法的C语言关键字是&#xff08;&#xff09;。 …...

【数据分析】层次贝叶斯

文章目录 一、 贝叶斯推理二、 层次贝叶斯模型三、 层次贝叶斯的特点四、 数学表述五、推断方法六、应用领域 层次贝叶斯&#xff08;Hierarchical Bayesian&#xff09;方法是一种基于贝叶斯推理的统计模型&#xff0c;用于处理具有多个层次结构的数据模型。 它允许我们在同一…...

Layui table不使用url属性结合laypage组件实现动态分页

从后台一次性获取所有数据赋值给 Layui table 组件的 data 属性&#xff0c;若数据量大时&#xff0c;很可能会超出浏览器字符串最大长度&#xff0c;导致渲染数据失败。Layui table 结合 laypage 组件实现动态分页可解决此问题。 HTML增加分页组件标签 在table后增加一个用于…...

【蓝桥杯】43688-《Excel地址问题》

Excel地址问题 题目描述 Excel 单元格的地址表示很有趣&#xff0c;它可以使用字母来表示列号。比如&#xff0c; A 表示第 1 列&#xff0c; B 表示第 2 列&#xff0c; … Z 表示第 26 列&#xff0c; AA 表示第 27 列&#xff0c; AB 表示第 28 列&#xff0c; … BA 表示…...

【bodgeito】攻防实战记录

也许有一天我们再相逢&#xff0c;睁开眼睛看清楚&#xff0c;我才是英雄。 进入网站整体浏览网页 点击页面评分进入关卡 一般搭建之后这里都是红色的&#xff0c;黄色是代表接近&#xff0c;绿色代表过关 首先来到搜索处本着见框就插的原则 构造payload输入 <script>…...

终极指南:如何将danger-js与Webpack集成实现自动化代码审查

终极指南&#xff1a;如何将danger-js与Webpack集成实现自动化代码审查 【免费下载链接】danger-js ⚠️ Stop saying "you forgot to …" in code review 项目地址: https://gitcode.com/gh_mirrors/da/danger-js Danger JS是一个强大的自动化代码审查工具&a…...

如何3步完成语雀文档迁移:新手终极免费指南

如何3步完成语雀文档迁移&#xff1a;新手终极免费指南 【免费下载链接】yuque-exporter export yuque to local markdown 项目地址: https://gitcode.com/gh_mirrors/yuq/yuque-exporter 还在为语雀平台策略调整而烦恼吗&#xff1f;担心自己的创作内容无处安放&#x…...

Pixel Aurora Engine基础教程:Streamlit状态管理与多会话隔离机制

Pixel Aurora Engine基础教程&#xff1a;Streamlit状态管理与多会话隔离机制 1. 认识Pixel Aurora Engine Pixel Aurora是一款基于AI扩散模型的高端绘图工作站&#xff0c;采用独特的复古像素游戏风格界面。这款"虚拟游戏机"能将文字描述转化为极具视觉冲击力的像…...

Python胶水代码变高性能引擎(Mojo原生编译实战手记)

第一章&#xff1a;Python胶水代码变高性能引擎&#xff08;Mojo原生编译实战手记&#xff09;Python 以其简洁语法和丰富生态成为数据科学与系统集成的“胶水语言”&#xff0c;但其解释执行机制常在数值计算、实时推理等场景遭遇性能瓶颈。Mojo 作为新兴的系统级编程语言&…...

JeecgBoot启动配置

一、引入maven指定自己的maven仓库 二、指定JDK 记得apply&#xff01;&#xff01;&#xff01;&#xff01;然后OK 三、配置MySQL数据库(尽量≥5.7版本) 四、运行db文件夹下的SQL文件 五、后端本地环境&#xff08;application-dev.yml&#xff09;指定好数据源 1、M…...

为什么99%的Python团队还没用上AOT?2026年官方方案的3大硬伤与2个绕过技巧(含patch diff与CI集成脚本)

第一章&#xff1a;Python 原生 AOT 编译方案 2026 概览与演进脉络Python 长期以来以解释执行和 JIT 辅助&#xff08;如 PyPy&#xff09;为主流运行范式&#xff0c;而原生 Ahead-of-Time&#xff08;AOT&#xff09;编译在 2026 年迎来实质性突破&#xff1a;CPython 官方正…...

腾讯云轻量服务器+宝塔面板:新手零代码搭建个人网站的保姆级避坑指南

腾讯云轻量服务器宝塔面板&#xff1a;新手零代码搭建个人网站的保姆级避坑指南 你是否曾经想过拥有一个属于自己的网站&#xff0c;却因为不懂代码和服务器运维而望而却步&#xff1f;现在&#xff0c;即使你没有任何技术背景&#xff0c;也能轻松实现这个梦想。本文将带你一步…...

Vivado Design Suite中BUFG优化策略与实战技巧

1. 理解BUFG的核心作用与设计痛点 在FPGA设计中&#xff0c;时钟信号就像人体神经系统中的电脉冲&#xff0c;需要快速、准确地传递到每个功能单元。BUFG&#xff08;全局时钟缓冲器&#xff09;就是Xilinx器件中专用的"信号放大器"&#xff0c;它能将时钟信号分配到…...

论文AIGC全红99%怎么救?2026实测Gemini去痕术:3组指令集联合3大工具,稳稳拉回10%安全线

视角重构&#xff0c;打破“平铺直叙”的机械感 AI生成的最大特征是“正确但平庸的上帝视角”。要ai降ai&#xff0c;第一步不是改词&#xff0c;而是强行植入一个具有批判性的“人类观察者”视角&#xff0c;迫使模型重组叙事逻辑。 核心原理&#xff1a;通过引入“辩证法”…...

STM32与LoRa实现高压线缆智能监控方案

1. 项目概述高压线缆间隔棒监控装置是一个典型的工业物联网应用案例&#xff0c;它完美展现了如何将嵌入式系统与无线通信技术结合解决传统行业的痛点问题。作为一名在电力监控领域工作多年的工程师&#xff0c;我深知人工巡检高压线路的种种不便——不仅效率低下&#xff0c;而…...