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

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...