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

串联所有单词的子串

题目链接

串联所有单词的子串

题目描述


注意点

  • words[i] 和 s 由小写英文字母组成
  • 1 <= words.length <= 5000
  • 可以以 任意顺序 返回答案
  • words中所有字符串长度相同

解答思路

  • 根据滑动窗口+哈希表解决本题,哈希表存储words中所有的单词及单词的出现次数,滑动窗口时使用另一个哈希表存储当前窗口内已经出现的单词及单词的出现次数
  • 因为words中所有字符串长度相同,所以在移动滑动窗口右边界时应该以单词为维度,每次移动wordLen个单位,然后判断该部分单词rightWord是否能作为串联串联所有单词的子串的一部分,有以下三种情况:
    • 如果rightWord根本不属于words中的单词,说明包含该单词时的子串一定不满足题意,此时需要将滑动窗口直接移动到该单词右侧,也就是直接重置滑动窗口的左右边界
    • 如果rightWord属于words中的单词,但是当前滑动窗口中该单词数量已经达到words中该单词的最大数量,此时需要移动滑动窗口的左边界,移动时每次也同样移动wordLen个单位,直到左侧找到一个与rightWord相同的值leftWord(一定能找到),将滑动窗口左边界移动到leftWord右侧
    • 如果rightWord属于words中的单词,且当前滑动窗口中该单词数量还未超过words中该单词的最大数量,此时满足题意,继续移动滑动窗口右边界(注意判断该滑动窗口已经是串联所有单词的子串的情况)
  • 上述过程并未判断所有情况,因为每次移动边界时都是以wordLen为单位,如果从字符串首位置开始,可能会忽略1,2…(wordLen - 1)为起始位置的情况,观察规律可得,只需要对1,2…(wordLen - 1)为起始位置都执行一次上述的操作就可以考虑到所有的情况

代码

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> res = new ArrayList<>();int wordSum = words.length;int wordLen = words[0].length();if (s.length() < wordSum * wordLen) {return res;}Map<String, Integer> map = new HashMap<>();for (String word : words) {map.put(word, map.getOrDefault(word, 0) + 1);}for (int i = 0; i < wordLen; i++) {int left = i;int right = i;int currWordSum = 0;Map<String, Integer> visitedMap = new HashMap<>();while (right + wordLen <= s.length()) {// 长度越界,剩下的子串一定无法串联所有单词if (left + (wordSum - currWordSum) * wordLen > s.length()) {break;}String leftWord = s.substring(left, left + wordLen);String rightWord = s.substring(right, right + wordLen);// 该单词不存在,则有该单词的部分都一定不满足题意,将滑动窗口左边界移动至该单词右侧if (map.get(rightWord) == null) {left = right + wordLen;visitedMap = new HashMap<>();currWordSum = 0;}// 该单词存在但words中已经没有该单词if (map.get(rightWord) != null && visitedMap.getOrDefault(rightWord, 0) >= map.get(rightWord)) {while (left < right && !rightWord.equals(leftWord)) {visitedMap.put(leftWord, visitedMap.get(leftWord) - 1);left += wordLen;leftWord = s.substring(left, left + wordLen);currWordSum--;}left += wordLen;}// 该单词存在满足题意if (map.get(rightWord) != null && visitedMap.getOrDefault(rightWord, 0) < map.get(rightWord)) {visitedMap.put(rightWord, visitedMap.getOrDefault(rightWord, 0) + 1);currWordSum++;// 已找到串联所有单词的子串if (currWordSum == wordSum) {res.add(left);visitedMap.put(leftWord, visitedMap.get(leftWord) - 1);currWordSum--;left += wordLen;}}right += wordLen;}}return res;}
}

关键点

  • 滑动窗口的思想
  • 移动滑动窗口时其对应的哈希表的变化
  • 移动滑动窗口右边界时对应单词是否是串联所有单词的子串的三种情况

相关文章:

串联所有单词的子串

题目链接 串联所有单词的子串 题目描述 注意点 words[i] 和 s 由小写英文字母组成1 < words.length < 5000可以以 任意顺序 返回答案words中所有字符串长度相同 解答思路 根据滑动窗口哈希表解决本题&#xff0c;哈希表存储words中所有的单词及单词的出现次数&#…...

【会议征稿通知】第四届经济发展与商业文化国际学术会议(ICEDBC2024)

第四届经济发展与商业文化国际学术会议&#xff08;ICEDBC2024&#xff09; The 4th International Conference on Economic Development and Business Culture (ICEDBC 2024) 第四届经济发展与商业文化国际学术会议&#xff08;ICEDBC2024&#xff09;将于2024年6月21-23日在…...

回溯算法套路③排列型回溯+N皇后【基础算法精讲 16】

46 . 全排列 链接 : . - 力扣&#xff08;LeetCode&#xff09; 思路 : 那么怎么确定选了那个数呢? 这里设置一个used表示i选没选过 ; class Solution { public:vector<vector<int>> ans;vector<int> path;void backtrack(vector<int>nums,vect…...

MyBatis-Plus 框架中的自定义元对象处理器

目录 一、代码展示二、代码解读 一、代码展示 package com.minster.yanapi.handler;import com.baomidou.mybatisplus.core.handlers.MetaObjectHandler; import org.apache.ibatis.reflection.MetaObject; import org.springframework.stereotype.Component;import java.util…...

Node.js_基础知识(fs模块 - 文件操作)

写入 文件操作 流式写入:fs.createWriteStream(path[, options]) 可以减少打开关闭文件的次数适用于:大文件写入、频繁写入参数说明: path:文件路径文件夹操作: 调用mkdir方法:fs.mkdir(./a/b/c, err => {}) 递归创建文件夹:加参数recursive fs.mkdir(./a/b/c, {recu…...

基于C#开发OPC DA客户端——搭建KEPServerEX服务

简介 OPC DA (OLE for Process Control Data Access) 是一种工业自动化领域中的通信协议标准&#xff0c;它定义了应用程序如何访问由OPC服务器提供的过程控制数据。OPC DA标准允许软件应用程序&#xff08;客户端&#xff09;从OPC服务器读取实时数据或向服务器写入数据&…...

让你的函数,返回你需要的“两个值” (函数传址、结构体作为参数传参)

总结&#xff1a;1.结构体完成你的目标 2.指针传参 方法2. void get_a_b(int* a, int* b) { *a 13; *b 14; //通过解引用&#xff0c;找到并修改 } int main() { int a 0; int b 0; get_a_b(&a, &b); //传地址 prin…...

快速上手:在 Android 设备上运行 Pipy

Pipy 作为一个高性能、低资源消耗的可编程代理&#xff0c;通过支持多种计算架构和操作系统&#xff0c;Pipy 确保了它的通用性和灵活性&#xff0c;能够适应不同的部署环境&#xff0c;包括但不限于云环境、边缘计算以及物联网场景。它能够在 X86、ARM64、海光、龙芯、RISC-V …...

【操作系统学习笔记】文件管理1.3

【操作系统学习笔记】文件管理1.3 参考书籍: 王道考研 视频地址: Bilibili I/O 控制方式 程序直接控制方式中断驱动方式DMA 方式通道控制方式 程序直接控制方式 关键词: 轮询 完成一次读/写操作的流程 CPU 向控制器发出读指令。于是设备启动&#xff0c;并且状态寄存器设…...

基于springboot+vue的酒店管理系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…...

Linux 相关命令

文章目录 目录相关操作vim 编辑器命令行模式插入模式底行模式 目录相关操作 查看当前目录下的文件 ls创建目录 mkdir 目录名进入文件&#xff0c;首先确认位于文件的目录 vi 文件名 vim 编辑器 命令行模式 控制光标的移动&#xff0c;字符或行的删除&#xff0c;移动复制某区域…...

阿里云搭建私有docker仓库(学习)

搭建私有云仓库 首先登录后直接在页面搜索栏中搜索“容器镜像服务” 进入后直接选择个人版&#xff08;可以免费使用&#xff09; 选择镜像仓库后创建一个镜像仓库 在创建仓库之前我们先创建一个命名空间 然后可以再创建我们的仓库&#xff0c;可以与我们的github账号进行关联…...

MySQL数据库基本操作(一)

数据库的基本概念 1. 数据库的英文单词&#xff1a; DataBase 简称 &#xff1a; DB 2. 什么数据库&#xff1f;* 用于存储和管理数据的仓库。 ​ 3. 数据库的特点&#xff1a;1. 持久化存储数据的。其实数据库就是一个文件系统2. 方便存储和管理数据3. 使用了统一的方式操作数…...

【暗月安全】2021年渗透测试全套培训视频

参与培训需要遵守国家法律法规&#xff0c;相关知识只做技术研究&#xff0c;请勿用于违法用途&#xff0c;造成任何后果自负与本人无关。 中华人民共和国网络安全法&#xff08;2017 年 6 月 1 日起施行&#xff09; 第二十二条 任何个人和组织不得从事入侵他人网络、干扰他…...

HTML极速入门

HTML基础 什么是HTML HTML(Hyper Text Markup Language),超文本标记语言. 超文本:比文本更强大.通过链接和交互式方式来组织和呈现信息的文本形式.不仅仅有文本,还可能包括图片,音频,或者自己经审阅过它的学者所加的评注,补充或脚注等. 标记语言:由标签构成的语言 HTML的标…...

Django框架——请求与响应

上篇文章我们学习了Django框架——配置文件和视图函数&#xff0c;这篇文章我们学习Django框架——请求与响应。 客户端和服务端的请求与响应过程&#xff1a;客户端访问某个网站并发出URL请求&#xff0c;服务器接受到请求后&#xff0c;根据请求内容来返回响应&#xff0c;如…...

rearrangement-challenge-2022环境使用学习(一)

搭建了rearrangement-challenge-2022的环境&#xff1a; https://github.com/facebookresearch/habitat-challenge/tree/rearrangement-challenge-2022 habitat最大的缺点是对不同的版本非常的敏感。本文只是针对rearrangement-challenge-2022的学习。 文档一开始会很不完善&a…...

[Uniapp]携带参数跳转界面(两种方法)

一、方法1&#xff1a;路由携参 假设现在有两个界面&#xff1a;界面A和界面B。并要由界面A跳转到界面B&#xff0c;则我们可以使用 uni.navigateTo({}) 跳转界面时&#xff0c;将参数附加在URL后&#xff0c…...

Scrapy与分布式开发(2.1.2):python常用网络请求库httpx

Python httpx 模块详细讲解 一、引言 httpx 是一个用于发送 HTTP 请求的 Python 库&#xff0c;它提供了简单易用的 API&#xff0c;支持同步和异步请求&#xff0c;并且具有出色的性能和灵活性。httpx 是 requests 的一个现代替代品&#xff0c;它使用 httpcore 作为底层传输…...

07. Nginx进阶-Nginx负载均衡

简介 负载均衡 什么是负载均衡&#xff1f; 负载均衡&#xff0c;英文名称为Load Balance&#xff0c;其含义就是指将负载&#xff08;工作任务&#xff09;进行平衡、分摊到多个操作单元上进行运行。 Nginx负载均衡 什么是Nginx负载均衡&#xff1f; Nginx负载均衡可以大…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL

ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...