算法-滑动窗口-串联所有单词的子串
算法-滑动窗口-串联所有单词的子串
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
1.2 题目描述


2 滑动窗口+Hash表
2.1 解题思路
- 构建一个大小为串联子串的总长的滑动窗口
- 为每个words中的子串创建一个hash表, <子串值,子串出现次数>
- 记录每次开始位置,从左往右遍历字符串s,每次截取words[0]长度的子串,和2中hash表对比,如果没有或者使用次数超限,就表示该组合无法构成,退出该次检测;否则继续检测,直到构成的串联子串长度满足要求或者已检测长度超限。构建成功时,记录下起始序号
- 一轮检测完成后,窗口向右滑动1个长度,继续下一轮检测
2.2 代码
class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> resultList = new ArrayList<>();int windowSize = words[0].length();if (windowSize > s.length()) {return resultList;}int strLength = windowSize * words.length;if (strLength > s.length()){return resultList;}Map<String, Integer> wordMap = new HashMap<>();for (int i = 0; i < words.length; i++) {Integer subKeyTimes = wordMap.get(words[i]);if (null == subKeyTimes) {subKeyTimes = 0;} wordMap.put(words[i], subKeyTimes + 1);}for (int i = 0; i <= s.length() - strLength; i++) {int result = getStart(s, words, strLength, windowSize, i, wordMap);if (result != -1) {resultList.add(result);}}return resultList;}private int getStart(String s, String[] words, int strLength, int windowSize, int first, Map<String, Integer> wordMap) {int start = -1;int length = 0;Map<String, Integer> useMap = new HashMap();for (int i = first; i < s.length() && length < strLength && i < first + strLength; i += windowSize) {String sub = s.substring(i, i + windowSize);Integer subKeyTimes = wordMap.get(sub);if (null == subKeyTimes) {return -1;}Integer useTimes = useMap.get(sub);if (null == useTimes) {useTimes = 1; } else {useTimes += 1;}if (useTimes > subKeyTimes) {return -1;}useMap.put(sub, useTimes);length += windowSize;if (start == -1) {start = i;}}if (length == strLength) {return start;}return -1;}
}
2.3 时间复杂度

s.length=n,words.length=m ,时间复杂度O(n*m)
2.4 空间复杂度
O(m)
3 回溯法+交换字符串
3.1 解题思路
3.2 代码
3.3 时间复杂度
3.4 空间复杂度
O(N)
相关文章:
算法-滑动窗口-串联所有单词的子串
算法-滑动窗口-串联所有单词的子串 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/substring-with-concatenation-of-all-words/ 1.2 题目描述 2 滑动窗口Hash表 2.1 解题思路 构建一个大小为串联子串的总长的滑动窗口为每个words中的子串创建一个hash表, <子…...
2023年7月京东美妆护肤品小样行业数据分析(京东数据挖掘)
如今,消费者更加谨慎,消费决策也更加理性。在这一消费环境下,美妆护肤市场中,面对动辄几百上千的化妆品,小样或体验装无疑能够降低消费者的试错成本。由此,这门生意也一直备受关注。 并且,小样…...
记录Taro巨坑,找不到sass类型定义文件
问题 taronutuisassts项目里tsconfig.json一直报红报错。 找不到“sass”的类型定义文件。 程序包含该文件是因为: 隐式类型库 “sass” 的入口点 其实正常人想的肯定是装上 types/sass试试。开始我试过了,没用。删了依赖重装也没用。后面在issue中找到答案了 解决…...
CS1988|C#无法在异步方法中使用ref,in,out类型的参数的问题
CS1988|C#无法在异步方法中使用ref,in,out类型的参数 🌀|场景: BlazorServer的场景中推荐使用异步方法,使用ref,out,in为参数前缀则报错CS1988 原因如下: ref parameters are not supported in async methods because the method may not h…...
ubuntu开机失败——ACPI Error
开机循环进入GNU GRUB 或者 黑屏 1.acpioff 解决办法 1)先用下面方法进入系统 2)更改grub ref 开机循环进入GNU GRUB 或者 黑屏 有提示ACPI Error错误如图: 解决办法 1)先用下面方法进入系统 在GUN GRUB界面,选择ubun…...
搭建开发环境-操作系统篇(一键搭建开发环境)
概述 所谓工欲善其事必先利其器,搭环境往往是开发过程中卡出很多初学者的拦路虎。 对于很多老鸟来说,很多东西都已经习惯成自然,也就没有刻意和初学者说。但对于很多初学者,却是受益良多。 这个系列,先从操作系统开始…...
人工智能AI绘画接入使用文档
人工智能AI绘画接入使用 一、人工智能AI绘画二、使用步骤1、接口2、请求参数3、请求参数示例4、接口 返回示例 三、 AI绘画优秀描述例子四、 如何获取appKey和uid1、申请appKey:2、获取appKey和uid 五、重要说明六、AI绘画成果展示 一、人工智能AI绘画 AI作画,用户可以在平台上…...
如何使用PyQt进行文件操作
PyQt是一个非常强大的Python GUI库,它可以帮助我们创建漂亮的跨平台应用程序。不过,在你开始使用PyQt进行文件操作之前,我想提醒你,这并不是在操作文件系统,而是在操作文件和文件夹。 首先,我们要导入PyQt…...
阿里云CDN加速器基本概念与购买开通
文章目录 1.CDN加速器的基本概念1.1.CDN加速器基本介绍1.2.网站引入CDN加速器的架构图1.3.CDN加速器的工作原理1.4.引入CDN后域名解析变成了CNAME? 2.开通阿里云CDN加速服务 1.CDN加速器的基本概念 CDN加速器官方文档:https://help.aliyun.com/product/…...
2023河南萌新联赛第(六)场:河南理工大学-F 爱睡大觉的小C
2023河南萌新联赛第(六)场:河南理工大学-F 爱睡大觉的小C https://ac.nowcoder.com/acm/contest/63602/F 文章目录 2023河南萌新联赛第(六)场:河南理工大学-F 爱睡大觉的小C题意解题思路 题意 新学期的概…...
[C++ 网络协议编程] 域名及网络地址
1. DNS服务器 DNS(Domain Name System):是对IP地址和域名(如:www.baidu.com等)进行相互转换的系统,其核心是DNS服务器。 我们输入的www.baidu.com是域名,是一种虚拟地址,而非实际地…...
Java【HTTP】什么是 Cookie 和 Session? 如何理解这两种机制的区别和作用?
文章目录 前言一、Cookie1, 什么是 Cookie2, Cookie 从哪里来3, Cookie 到哪里去4, Cookie 有什么用 二、Session1, 什么是 Session2, 理解 Session 三、Cookie 和 Session 的区别总结 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 …...
使用U盘重装Windows10系统详细步骤及配图【官方纯净版】
文章目录 1.制作启动盘1.1准备U盘及一台电脑1.2下载win10安装包 2.安装操作系统2.1插入系统安装盘2.2设置启动盘为第一启动项2.3开始安装操作系统 3.安装成功后进入图形界面3.1启动问题3.2驱动问题3.3调出"控制面板"3.4给磁盘分区 4.win10激活 前天下午不知道怎么想的…...
数据结构之——(手撕)顺序表
本章会介绍的知识点如下图: 1: 顺序表的概念:顺序表是用一段物理地址连续的存储单元依次存储数据的线性结构,通常我们使用数组来表示,对数组进行增删查改。 顺序表的结构:逻辑结构与物理结构都是内存中一块…...
冠达管理:非银金融是什么?
非银金融(Non-banking Financial Institutions,简称非银)是指除了传统的银行以外的其他金融机构。与银行不同的是,非银金融机构没有颁发钱银的权利,但在金融市场中发挥着重要的效果。在全球范围内,非银金融…...
go 结构体
定义结构体 package mainimport "fmt"type Person struct {age, id intname, email string }func main() {var p Personfmt.Printf("p: %v\n", p)p.age 100p.name "jaja"fmt.Printf("p.name: %v\n", p.name)// 匿名结构体var P…...
C++学习笔记---- 引用
1、作用 给变量起别名 基本语法:数据类型 &别名 原名 示例: #include <iostream> using namespace std;int main() {int a 1;int &b a;cout << "a " << a << endl;cout << "b " <…...
2023国赛数学建模思路 - 案例:感知机原理剖析及实现
文章目录 1 感知机的直观理解2 感知机的数学角度3 代码实现 4 建模资料 # 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 感知机的直观理解 感知机应该属于机器学习算法中最简单的一种算法,其…...
Cesium加载Supermap的wmts服务
最近使用cesium 加载supermap的wmts 服务,多次遇到加载异常与白页面问题,纠结好久最后才搞定[特此记录] 1、首先找到方法加载wmts 的api 文档 官方提示使用WebMapTileServiceImageryProvider加载wmts 2、然后编辑加载代码 //1.新建ImageryProviderlet…...
C/C++:C/C++在大数据时代的应用,以及C/C++程序员未来的发展路线
目录 1.C/C在大数据时代的应用 1.1:C/C数据处理 1.2:C/C数据库 1.3:C/C图像处理和计算机视觉 1.3.1:导读 2.C/C程序员未来的发展路线 2.1:图导 1.C/C在大数据时代的应用 C/C在大数据时代中仍然是一种被广泛应用的编…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
