2.7 滑动窗口专题:串联所有单词的子串

LeetCode 30. 串联所有单词的子串算法对比分析


1. 题目链接

LeetCode 30. 串联所有单词的子串


2. 题目描述

给定一个字符串 s 和一个字符串数组 wordswords 中所有单词长度相同。要求找到 s 中所有起始索引,使得从该位置开始的连续子串包含 words 中所有单词的某种排列(不限制顺序)。
示例
输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9](子串 "barfoo""foobar" 符合条件)。


3. 算法思路

滑动窗口法

  1. 问题转化:将 words 的排列匹配问题转化为固定窗口长度的滑动窗口问题。
  2. 哈希表统计:用 hash1 记录 words 中单词的出现次数,hash2 记录当前窗口内单词的出现次数。
  3. 多起点遍历:由于单词长度固定为 nwSub,需遍历 nwSub 种可能的起始偏移(0 ≤ i < nwSub)。
  4. 窗口动态调整
    • 右指针扩展:每次截取一个单词加入窗口,更新哈希表。
    • 左指针收缩:当窗口内单词数量超过 nw 时,移动左指针。
  5. 结果判断:当窗口内单词数量等于 nw 且所有单词频率匹配时,记录起始索引。

暴力枚举法

  1. 遍历所有子串:枚举所有长度为 nw * nwSub 的子串。
  2. 分割统计:将子串分割为 nw 个单词,统计频率是否与 words 一致。

4. 示例分析

输入:s = "barfoothefoobarman", words = ["foo","bar"]

  1. 暴力枚举法

    • 枚举所有长度为 6 的子串,例如 "barfoo", "arfoot", "rfooth" 等。
    • 对每个子串分割为 ["bar","foo"]["arf","oot"],检查是否与 words 匹配。
  2. 滑动窗口法

    • i=0 时,窗口从 left=0 开始,截取 "bar""foo"count=2,记录索引 0。
    • i=9 时,窗口从 left=9 开始,截取 "foo""bar"count=2,记录索引 9。

5. 边界条件与注意事项
  1. 单词长度相同words 中所有单词长度必须一致。
  2. 空输入处理:若 words 为空或 s 长度不足,直接返回空。
  3. 哈希表更新:需在收缩窗口时及时减少 hash2 的计数,避免无效单词干扰。

6. 代码实现
class Solution 
{
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;int ns = s.size(), nw = words.size(), nwSub = words[0].size();if (ns < nwSub * nw) return ret;unordered_map<string, int> hash1;for (auto& word : words) hash1[word]++;for (int i = 0; i < nwSub; i++) { // 遍历所有可能的起始偏移unordered_map<string, int> hash2;int left = i, count = 0; // left为窗口左边界for (int right = i; right + nwSub <= ns; right += nwSub) {// 截取当前单词string in = s.substr(right, nwSub);hash2[in]++;// 更新有效计数:仅在当前单词属于hash1且未超过次数时增加countif (hash1.count(in) && hash2[in] <= hash1[in]) count++;// 当窗口内的单词数量超过nw时,收缩左边界while ((right - left) / nwSub + 1 > nw) {string out = s.substr(left, nwSub);if (hash1.count(out) && hash2[out] <= hash1[out]) count--;hash2[out]--;left += nwSub; // 左指针移动一个单词长度}// 若有效计数等于nw,记录起始索引if (count == nw) ret.push_back(left);}}return ret;}
};

在这里插入图片描述


7.暴力枚举法与滑动窗口法对比图表
对比维度暴力枚举法滑动窗口法
核心思想枚举所有长度为 nw * nwSub 的子串,分割后比较单词频率。维护固定窗口长度,动态调整窗口内的单词频率。
时间复杂度O(ns * nw * nwSub)(每个子串需分割并统计频率)。O(ns * nwSub)(每个单词被处理一次)。
空间复杂度O(nw)(存储 words 的哈希表)。O(nw)(存储两个哈希表)。
实现方式双重循环遍历子串,内层循环分割并统计。单层循环扩展右指针,动态调整左指针。
适用场景小规模数据(ns ≤ 1e3, nw ≤ 10)。大规模数据(ns ≤ 1e5)。
优点逻辑简单,直接穷举所有可能性。时间复杂度低,适用于大规模数据。
缺点数据规模大时性能极差(例如 ns=1e4 时需 1e8 次操作)。需处理哈希表的动态更新和边界条件。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34982.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue中,watch里,this为undefined的两种解决办法

提示&#xff1a;vue中&#xff0c;watch里&#xff0c;this为undefined的两种解决办法 文章目录 [TOC](文章目录) 前言一、问题二、方法1——使用function函数代替箭头函数()>{}三、方法2——使用that总结 前言 ‌‌‌‌‌尽量使用方法1——使用function函数代替箭头函数()…

uniapp移动端图片比较器组件,仿英伟达官网rtx光追图片比较器功能

组件下载地址&#xff1a;https://ext.dcloud.net.cn/plugin?id22609 已测试h5和微信小程序&#xff0c;理论支持全平台 亮点&#xff1a; 简单易用 使用js计算而不是resize属性&#xff0c;定制化程度更高 组件挂在后可播放指示线动画&#xff0c;提示用户可以拖拽比较图片…

SDL3 游戏开发 Windows 环境搭建

SDL3 游戏开发 Windows 环境搭建 一、准备工作1.1 必备工具与库安装1.1.1 CMake1.1.2 MinGW-w641.1.3 Ninja1.1.4 Git1.1.5 SDL3 及扩展库1.1.6 VSCode 及插件 二、配置VSCode项目并验证环境2.1 创建测试源文件2.2 编写CMakeLists.txt文件和CMakePresets.json2.2.1 使用VSCode的…

【sql靶场】第13、14、17关-post提交报错注入保姆级教程

目录 【sql靶场】第13、14、17关-post提交报错注入保姆级教程 1.知识回顾 1.报错注入深解 2.报错注入格式 3.使用的函数 4.URL 5.核心组成部分 6.数据编码规范 7.请求方法 2.第十三关 1.测试闭合 2.列数测试 3.测试回显 4.爆出数据库名 5.爆出表名 6.爆出字段 …

esxi,vcenter6.0安装指导

前言 esxi6.0安装和esxi6.7步骤基本一样&#xff0c;可参考vmware esxi vcenter6.7安装教程&#xff08;dell&#xff09; 环境依赖以及安装包 esxi6.0安装包vcenter6.0安装不同于6.7&#xff0c;6.5通过导入ova模版安装&#xff0c;需要安装在windows server 2008或者windo…

BigFoot Decursive lua

BigFoot Decursive lua 一键驱散脚本 国际化 ogg语音提示 初始化

2024山东大学计算机复试上机真题

2024山东大学计算机复试上机真题 2024山东大学计算机复试机试真题 历年山东大学计算机复试上机真题 历年山东大学计算机复试机试真题 在线评测&#xff1a;传动门&#xff1a;pgcode.cn 最长递减子序列 题目描述 输入数字 n&#xff0c;和 n 个整数&#xff0c;输出该数字…

【AI News | 20250316】每日AI进展

AI Repos 1、ReActMCP 将网络搜索能力集成到AI助手中的一个MCP服务&#xff1a;ReActMCP Web Search&#xff0c;相当于给AI装了个搜索引擎&#xff0c;可以实时查找最新的内容。它基于Exa API执行基本和高级网络搜索&#xff0c;高级搜索比如限制搜索的网站范围、指定日期范围…

【大模型实战篇】使用GPTQ量化QwQ-32B微调后的推理模型

1. 量化背景 之所以做量化&#xff0c;就是希望在现有的硬件条件下&#xff0c;提升性能。量化能将模型权重从高精度&#xff08;如FP32&#xff09;转换为低精度&#xff08;如INT8/FP16&#xff09;&#xff0c;内存占用可减少50%~75%。低精度运算&#xff08;如INT8&#xf…

Unity 笔记:在EditorWindow中绘制 Sorting Layer

在Unity开发过程中&#xff0c;可能会对旧资源进行批量修改&#xff0c;一个个手动修改费人费事&#xff0c;所以催生出了一堆批量工具。 分享一下在此过程中绘制 Sorting Layer 面板的代码脚本。 示意图&#xff1a; 在 EditorGUI 和 EditorGUILayer 中内置了 SortingLayerF…

idea更新git代码报错No Git Roots

idea更新git代码报错&#xff1a; No Git Roots None of configured Git roots are under Git. The configured directory must have ".git directory in it.但是本地项目里是存在.git文件的&#xff0c;就是突然间不能更新代码了 然后尝试重新拉新项目代码提示: Git i…

失败的面试经历(ʘ̥∧ʘ̥)

一.面向对象的三大特性 1.封装&#xff1a;将对象内部的属性私有化&#xff0c;外部对象不能够直接访问&#xff0c;但是可以提供一些可以使外部对象操作内部属性的方法。 2.继承&#xff1a;类与类之间会有一些相似之处&#xff0c;但也会有一些异处&#xff0c;使得他们与众…

qt加载VeloView工程

接上一篇点云软件配置与编译&#xff0c;使用qt加载需要先完成编译。编译完成后到编译目录下lidarview-superbuild\common-superbuild\lidarview\build 找到CmakeCache.txt&#xff0c;如下是我的编译目录。 使用QT6.5.3加载了CmakeCache.txt&#xff0c;QT5.14还加载不了cmake…

Windows Qt动态监测系统分辨率及缩放比变化

前言 Windows 显示设置中&#xff0c;可以修改缩放比&#xff0c;所有界面和文字会同比例放大或缩小&#xff0c;在开发桌面程序时&#xff0c; 实时监测Qt应用程序在不同缩放比例下的表现&#xff0c;可以及时调整程序界面以适应不同显示屏幕的需求。 正文 本文通过Qt相关…

CVE-2017-5645(使用 docker 搭建)

介绍: 是一个与 Apache Log4j2 相关的安全漏洞,属于远程代码执行,它可能允许攻击者通过构造恶意的日志信息 在目标系统上执行任意代码 Log4j2 介绍 Log4j2 是 Apache 的一个日志记录工具,属于 Java 应用的日志框架,它是 Log4j 的升级版,性能更好,功能更多.它被广泛的适用于 J…

交互式可视化进阶(Plotly Dash构建疫情仪表盘)

这里写目录标题 交互式可视化进阶(Plotly Dash构建疫情仪表盘)1. 引言2. 项目背景与意义3. 数据集生成与介绍4. GPU加速在数据处理中的应用5. 交互式仪表盘构建与Plotly Dash6. PyQt GUI集成与美化7. 工程整体架构8. 部分代码实现9. 代码自查与BUG排查10. 总结与展望交互式可…

RabbitMQ(补档)

RabbitMQ 是一个开源的消息队列软件&#xff08;有时也被称为消息代理&#xff09;&#xff0c;它实现了高级消息队列协议&#xff08;AMQP&#xff09;。它主要用于应用程序之间&#xff0c;或者软件组件之间的消息通信。通过使用 RabbitMQ&#xff0c;可以实现异步的、可靠的…

平方矩阵问题

Ⅰ 回字形二维数组 #include <iostream> #include <iomanip> using namespace std; int main(){int n;while(cin>>n,n){for(int i0; i<n;i){for(int j0; j<n; j){int upi, downn-i1, leftj, rightn-j1;cout<<min(min(up,down),min(left,right)…

电子电气架构 --- 智能座舱和车载基础软件简介

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 人生是一场骗局,最大的任务根本不是什么买车买房,也不是及时行乐,这就是欲望,不是理想,是把自己对生命的希望寄托在外物上,正确的做法应该是内…