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

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...