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

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

麒麟系统使用-进行.NET开发

文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的&#xff0c;如果需要进行.NET开发&#xff0c;则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET&#xff0c;所以要进…...

深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学

一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件&#xff0c;其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时&#xff0c;价带电子受激发跃迁至导带&#xff0c;形成电子-空穴对&#xff0c;导致材料电导率显著提升。…...

python打卡day49@浙大疏锦行

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 一、通道注意力模块复习 & CBAM实现 import torch import torch.nn as nnclass CBAM(nn.Module):def __init__…...