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

算法-滑动窗口-串联所有单词的子串

算法-滑动窗口-串联所有单词的子串

1 题目概述

1.1 题目出处

https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

1.2 题目描述

在这里插入图片描述
在这里插入图片描述

2 滑动窗口+Hash表

2.1 解题思路

  1. 构建一个大小为串联子串的总长的滑动窗口
  2. 为每个words中的子串创建一个hash表, <子串值,子串出现次数>
  3. 记录每次开始位置,从左往右遍历字符串s,每次截取words[0]长度的子串,和2中hash表对比,如果没有或者使用次数超限,就表示该组合无法构成,退出该次检测;否则继续检测,直到构成的串联子串长度满足要求或者已检测长度超限。构建成功时,记录下起始序号
  4. 一轮检测完成后,窗口向右滑动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月京东美妆护肤品小样行业数据分析(京东数据挖掘)

如今&#xff0c;消费者更加谨慎&#xff0c;消费决策也更加理性。在这一消费环境下&#xff0c;美妆护肤市场中&#xff0c;面对动辄几百上千的化妆品&#xff0c;小样或体验装无疑能够降低消费者的试错成本。由此&#xff0c;这门生意也一直备受关注。 并且&#xff0c;小样…...

记录Taro巨坑,找不到sass类型定义文件

问题 taronutuisassts项目里tsconfig.json一直报红报错。 找不到“sass”的类型定义文件。 程序包含该文件是因为: 隐式类型库 “sass” 的入口点 其实正常人想的肯定是装上 types/sass试试。开始我试过了&#xff0c;没用。删了依赖重装也没用。后面在issue中找到答案了 解决…...

CS1988|C#无法在异步方法中使用ref,in,out类型的参数的问题

CS1988|C#无法在异步方法中使用ref,in,out类型的参数 &#x1f300;|场景&#xff1a; BlazorServer的场景中推荐使用异步方法&#xff0c;使用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&#xff09;先用下面方法进入系统 2&#xff09;更改grub ref 开机循环进入GNU GRUB 或者 黑屏 有提示ACPI Error错误如图&#xff1a; 解决办法 1&#xff09;先用下面方法进入系统 在GUN GRUB界面&#xff0c;选择ubun…...

搭建开发环境-操作系统篇(一键搭建开发环境)

概述 所谓工欲善其事必先利其器&#xff0c;搭环境往往是开发过程中卡出很多初学者的拦路虎。 对于很多老鸟来说&#xff0c;很多东西都已经习惯成自然&#xff0c;也就没有刻意和初学者说。但对于很多初学者&#xff0c;却是受益良多。 这个系列&#xff0c;先从操作系统开始…...

人工智能AI绘画接入使用文档

人工智能AI绘画接入使用 一、人工智能AI绘画二、使用步骤1、接口2、请求参数3、请求参数示例4、接口 返回示例 三、 AI绘画优秀描述例子四、 如何获取appKey和uid1、申请appKey:2、获取appKey和uid 五、重要说明六、AI绘画成果展示 一、人工智能AI绘画 AI作画,用户可以在平台上…...

如何使用PyQt进行文件操作

PyQt是一个非常强大的Python GUI库&#xff0c;它可以帮助我们创建漂亮的跨平台应用程序。不过&#xff0c;在你开始使用PyQt进行文件操作之前&#xff0c;我想提醒你&#xff0c;这并不是在操作文件系统&#xff0c;而是在操作文件和文件夹。 首先&#xff0c;我们要导入PyQt…...

阿里云CDN加速器基本概念与购买开通

文章目录 1.CDN加速器的基本概念1.1.CDN加速器基本介绍1.2.网站引入CDN加速器的架构图1.3.CDN加速器的工作原理1.4.引入CDN后域名解析变成了CNAME&#xff1f; 2.开通阿里云CDN加速服务 1.CDN加速器的基本概念 CDN加速器官方文档&#xff1a;https://help.aliyun.com/product/…...

2023河南萌新联赛第(六)场:河南理工大学-F 爱睡大觉的小C

2023河南萌新联赛第&#xff08;六&#xff09;场&#xff1a;河南理工大学-F 爱睡大觉的小C https://ac.nowcoder.com/acm/contest/63602/F 文章目录 2023河南萌新联赛第&#xff08;六&#xff09;场&#xff1a;河南理工大学-F 爱睡大觉的小C题意解题思路 题意 新学期的概…...

[C++ 网络协议编程] 域名及网络地址

1. DNS服务器 DNS&#xff08;Domain Name System&#xff09;&#xff1a;是对IP地址和域名&#xff08;如:www.baidu.com等&#xff09;进行相互转换的系统&#xff0c;其核心是DNS服务器。 我们输入的www.baidu.com是域名&#xff0c;是一种虚拟地址&#xff0c;而非实际地…...

Java【HTTP】什么是 Cookie 和 Session? 如何理解这两种机制的区别和作用?

文章目录 前言一、Cookie1, 什么是 Cookie2, Cookie 从哪里来3, Cookie 到哪里去4, Cookie 有什么用 二、Session1, 什么是 Session2, 理解 Session 三、Cookie 和 Session 的区别总结 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: &#x1f4d5; …...

使用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激活 前天下午不知道怎么想的…...

数据结构之——(手撕)顺序表

本章会介绍的知识点如下图&#xff1a; 1&#xff1a; 顺序表的概念&#xff1a;顺序表是用一段物理地址连续的存储单元依次存储数据的线性结构&#xff0c;通常我们使用数组来表示&#xff0c;对数组进行增删查改。 顺序表的结构&#xff1a;逻辑结构与物理结构都是内存中一块…...

冠达管理:非银金融是什么?

非银金融&#xff08;Non-banking Financial Institutions&#xff0c;简称非银&#xff09;是指除了传统的银行以外的其他金融机构。与银行不同的是&#xff0c;非银金融机构没有颁发钱银的权利&#xff0c;但在金融市场中发挥着重要的效果。在全球范围内&#xff0c;非银金融…...

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、作用 给变量起别名 基本语法&#xff1a;数据类型 &别名 原名 示例&#xff1a; #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 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 感知机的直观理解 感知机应该属于机器学习算法中最简单的一种算法&#xff0c;其…...

Cesium加载Supermap的wmts服务

最近使用cesium 加载supermap的wmts 服务&#xff0c;多次遇到加载异常与白页面问题&#xff0c;纠结好久最后才搞定[特此记录] 1、首先找到方法加载wmts 的api 文档 官方提示使用WebMapTileServiceImageryProvider加载wmts 2、然后编辑加载代码 //1.新建ImageryProviderlet…...

C/C++:C/C++在大数据时代的应用,以及C/C++程序员未来的发展路线

目录 1.C/C在大数据时代的应用 1.1&#xff1a;C/C数据处理 1.2&#xff1a;C/C数据库 1.3&#xff1a;C/C图像处理和计算机视觉 1.3.1&#xff1a;导读 2.C/C程序员未来的发展路线 2.1&#xff1a;图导 1.C/C在大数据时代的应用 C/C在大数据时代中仍然是一种被广泛应用的编…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...