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

【算法题】30. 串联所有单词的子串

题目

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd","cdabef", "cdefab","efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1:

输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2:

输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3:

输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]
解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
 

提示:

1 <= s.length <= 10^4
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

题解

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> res = new ArrayList<Integer>();int m = words.length, n = words[0].length(), ls = s.length();for (int i = 0; i < n; i++) {if (i + m * n > ls) {break;}Map<String, Integer> differ = new HashMap<String, Integer>();for (int j = 0; j < m; j++) {String word = s.substring(i + j * n, i + (j + 1) * n);differ.put(word, differ.getOrDefault(word, 0) + 1);}for (String word : words) {differ.put(word, differ.getOrDefault(word, 0) - 1);if (differ.get(word) == 0) {differ.remove(word);}}for (int start = i; start < ls - m * n + 1; start += n) {if (start != i) {String word = s.substring(start + (m - 1) * n, start + m * n);differ.put(word, differ.getOrDefault(word, 0) + 1);if (differ.get(word) == 0) {differ.remove(word);}word = s.substring(start - n, start);differ.put(word, differ.getOrDefault(word, 0) - 1);if (differ.get(word) == 0) {differ.remove(word);}}if (differ.isEmpty()) {res.add(start);}}}return res;}
}

来自力扣官方题解

相关文章:

【算法题】30. 串联所有单词的子串

题目 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如&#xff0c;如果 words ["ab","cd","ef"]&#xff0c; 那么 "…...

SAP-FI模块 处理自动生成会计凭证增强

ENHANCEMENT 2 ZEHENC_SAPMF05A. "active version * FI 20221215&#xff1a;固定资产业务过渡科目摘要增强功能 WAIT UP TO 1 SECONDS.READ TABLE xbseg WITH KEY hkont 1601990001. IF sy-subrc 0.DATA: lt_bkdf TYPE TABLE OF bkdf,lt_bkpf TYPE TABLE OF bkpf,…...

Shell脚本-bin/bash: 解释器错误: 没有那个文件或目录-完整路径执行-“/”引发的脑裂

引起该不适的一种可能以及解决方案&#xff0c;网上较多&#xff0c;比如&#xff1a; 但按以上方式操作&#xff0c;并经过查看&#xff0c;发现仍然未能解决问题。 因为两种方式执行&#xff0c;有一种能成功&#xff0c;有一种不能&#xff0c;刚开始未怀疑是文件问题&…...

React MUI(版本v5.15.2)详细使用

使用React MUI&#xff08;版本v5.15.2&#xff09;的详细示例。请注意&#xff0c;由于版本可能会有所不同&#xff0c;因此建议您查阅官方文档以获取最新的信息和示例。但是&#xff0c;我将根据我的知识库为您提供一些基本示例。 首先&#xff0c;确保您已经按照之前的说明…...

用CSS中的动画效果做一个转动的表

<!DOCTYPE html> <html lang"en"><head><meta charset"utf-8"><title></title><style>*{margin:0;padding:0;} /*制作表的样式*/.clock{width: 500px;height: 500px;margin:0 auto;margin-top:100px;border-rad…...

【linux】Linux管道的原理与使用场景

Linux管道是Linux命令行界面中一种强大的工具&#xff0c;它允许用户将多个命令链接起来&#xff0c;使得一个命令的输出可以作为另一个命令的输入。这种机制使得我们可以创建复杂的命令链&#xff0c;并在处理数据时提供了极大的灵活性。在本文中&#xff0c;我们将详细介绍Li…...

nvidia jetson xavier nx developer kit version emmc版重装系统

一、将开发板上的外置硬盘取下来格式化 二、在双系统ubuntu安装SDK Manager&#xff08;.deb文件&#xff09; SDK Manager | NVIDIA Developer sudo apt install ./sdkmanager_1.9.2-10884_amd64.deb 报错直接百度错误&#xff0c;执行相应命令即可 三、 运行SDK Manager …...

命令模式-实例使用

未使用命令模式的UML 使用命令模式后的UML public abstract class Command {public abstract void execute(); }public class Invoker {private Command command;/*** 为功能键注入命令* param command*/public void setCommand(Command command) {this.command command;}/***…...

将网页变身移动应用:网址封装成App的完全指南

什么是网址封装&#xff1f; 网址封装是一个将你的网站或网页直接嵌入到一个原生应用容器中的过程。用户可以通过下载你的App来访问网站&#xff0c;而无需通过浏览器。这种方式不仅提升了用户体验&#xff0c;还可利用移动设备的功能&#xff0c;如推送通知和硬件集成。 小猪…...

探讨kernel32.dll文件是什么,有效解决kernel32.dll丢失

在使用电脑时&#xff0c;你是否遇到过kernel32.dll丢失的困扰&#xff1f;面对这个问题&#xff0c;我们需要及时去解决kernel32.dll丢失的问题。接下来&#xff0c;我们将深入探讨kernel32.dll的功能以及其在操作系统和应用程序中的具体应用领域&#xff0c;相信这将对你解决…...

LOAM: Lidar Odometry and Mapping in Real-time 论文阅读

论文链接 LOAM: Lidar Odometry and Mapping in Real-time 0. Abstract 提出了一种使用二维激光雷达在6自由度运动中的距离测量进行即时测距和建图的方法 距离测量是在不同的时间接收到的&#xff0c;并且运动估计中的误差可能导致生成的点云的错误配准 本文的方法在不需要高…...

如何使用Docker将.Net6项目部署到Linux服务器(三)

目录 四 安装nginx 4.1 官网下载nginx 4.2 下载解压安装nginx 4.3 进行configure 4.4 执行make 4.5 查看nginx是否安装成功 4.6 nginx的一些常用命令 4.6.1 启动nginx 4.6.2 通过命令查看nginx是否启动成功 4.6.3 关闭Nginx 4.6.5 重启Nginx 4.6.6 杀掉所有Nginx进程 4.…...

《Spring Cloud学习笔记:分布式事务Seata》

解决分布式事务的方案有很多&#xff0c;但实现起来都比较复杂&#xff0c;因此我们一般会使用开源的框架来解决分布式事务问题。 在众多的开源分布式事务框架中&#xff0c;功能最完善、使用最多的就是阿里巴巴在2019年开源的Seata了。 1. 初识Seata Seata是 2019 年 1 月…...

MySQL:权限控制

要授予用户帐户权限&#xff0c;可以用GRANT命令。有撤销用户的权限&#xff0c;可以用REVOKE命令。这里以 MySQl 为例&#xff0c;介绍权限控制实际应用。 GRANT授予权限语法&#xff1a; GRANT privilege,[privilege],.. ON privilege_level TO user [IDENTIFIED BY passwo…...

安全生产知识竞赛活动方案

为进一步普及安全生产法律法规知识&#xff0c;增强安全意识&#xff0c;提高安全技能&#xff0c;经研究&#xff0c;决定举办以“加强安全法治、保障安全生产”为主题的新修订《安全生产法》知识竞赛活动&#xff0c;现将有关事项通知如下&#xff1a; 一、活动时间&#xf…...

2023 IoTDB Summit:天谋科技 CTO 乔嘉林《IoTDB 企业版 V1.3: 时序数据管理一站式解决方案》...

12 月 3 日&#xff0c;2023 IoTDB 用户大会在北京成功举行&#xff0c;收获强烈反响。本次峰会汇集了超 20 位大咖嘉宾带来工业互联网行业、技术、应用方向的精彩议题&#xff0c;多位学术泰斗、企业代表、开发者&#xff0c;深度分享了工业物联网时序数据库 IoTDB 的技术创新…...

LangChain.js 实战系列:如何统计大模型使用的 token 使用量和花费

&#x1f4dd; LangChain.js 是一个快速开发大模型应用的框架&#xff0c;它提供了一系列强大的功能和工具&#xff0c;使得开发者能够更加高效地构建复杂的应用程序。LangChain.js 实战系列文章将介绍在实际项目中使用 LangChain.js 时的一些方法和技巧。 统计调用大模型的 to…...

基于多反应堆的高并发服务器【C/C++/Reactor】(中)EventLoop初始化

这个Dispatcher是一个事件分发模型&#xff0c;通过这个模型,就能够检测对应的文件描述符的事件的时候,可以使用epoll/poll/select,前面说过三选一。另外不管是哪一个底层的检测模型,它们都需要使用一个数据块,这个数据块就叫做DispatcherData。除此之外,还有另外一个部分,因为…...

OpenCV(Python)基础—9小时入门版

OpenCV(Python)基础—9小时入门版 # # Author : Mikigo # Time : 2021/12/1 # 一、一句话简介 OpenCV (Open Source Computer Vision Library) 是用 C 语言编写&#xff0c;提供 Python、Java 等语言 API的一个开源计算机视觉库。 二、安装 1、Debian 系使用 apt 安装 O…...

SpringBoot整合Canal

一 linux docker compose版本 1.第一步&#xff1a;基础环境 &#xff08;1&#xff09;第1步&#xff1a;安装jak、maven、git、nodejs、npm yum install maven mvn -v 安装maven时会帮安装jdkyum install git git --version 2.27.0yum in…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...