面试经典150题——串联所有单词的子串(困难)

"Opportunities don't happen, you create them." ​

- Chris Grosser

gray concrete road between brown and green leaf trees at daytime

1. 题目描述

2.  题目分析与解析

2.1 思路一——暴力求解

遇见这种可能刚开始没什么思路的问题,先试着按照人的思维来求解该题目。对于一个人来讲,我想要找到 s 字符串中包含 words 中所有字符串以任意顺序排列连接起来的子串的开始索引,那么我可能会有这种思路:

// 初始化wordsAndCount
for (String word : words) {
    wordsAndCount.put(word, wordsAndCount.getOrDefault(word, 0) + 1);
}

  • 遍历字符串 s

  • 对于每一个字符开头的与words中字符串长度相同的子串,尝试在words中匹配

    • 如果匹配成功,就需要将words中当前字符串删除,下一次就从当前字符 + words[i].length处开始继续匹配,以此循环,直到words为空,记录起始下标。

    • 如果匹配失败,从下一个字符处继续重新匹配。

  • 同时需要注意由于words中可能有相同的单词,因此我们需要记录如果是相同单词其出现的次数,这样就方便在遍历时删除,只需要将对应的值减一,当减到0就从words中删除该单词即可。初始化可以按照如下方式:

但是显然这种方法非常的耗时,因为对于每一个S字符串的字符你都需要查找是否匹配,最坏的情况下需要走完words的总长度,因此总遍历为S的长度 N 乘以 words的长度 M。但是起码我们能够解决问题,这能给我们一点自信再去想怎么优化,所以遇到问题先想想人怎么解决,没有思路的情况下就先不要太在意时间复杂度。

我按照如下的代码运行如预期会超时:

2.2 思路二——滑动窗口

对于这种一块一块的内容去对比的问题,我们应该敏锐的去想能不能用滑动窗口解决。刚好我在这也稍微总结一下什么情况下可以使用滑动窗口来解决,这样我们遇到新的题目就能更快速的想到可能的解决办法,再去尝试。

滑动窗口思想运用场景

滑动窗口技术是一种用于解决数组或列表相关问题的算法策略,特别适用于需要处理连续数据段的问题。这种技术广泛应用于各种场景,尤其是在需要优化时间和空间复杂度的场合。

  1. 最大/最小子数组问题:当你需要找到数组中某个大小的连续子数组,使得其和最大或最小时,滑动窗口技术可以有效地解决问题。

  2. 固定大小的问题:对于需要处理固定大小窗口的问题,如计算给定大小的窗口内的平均值、最大值或最小值,滑动窗口是一个理想的解决方案。

  3. 可变大小的问题:对于窗口大小不固定的问题,如找到数组中和至少为K的最短子数组,滑动窗口技术可以通过动态调整窗口大小来寻找最优解。

  4. 字符串匹配问题:在处理字符串时,如查找字符串中包含所有字符的最短子串,滑动窗口能够有效地跟踪字符出现的情况。

  5. 计数问题:当需要计数或统计特定条件下的连续子数组(或子序列)数量时,滑动窗口可以在遍历数组的同时维护这些统计信息。

  6. 双指针问题:在一些双指针问题中,滑动窗口可以视为一种特殊的双指针实现,尤其是当问题涉及到连续序列或子数组时。

  7. 连续序列问题:需要找到满足特定条件的连续序列时,如和为特定值的连续正数序列,滑动窗口提供了一种高效的解决方案。

滑动窗口技术之所以强大,是因为它能够在遍历数据的同时,通过调整窗口的大小或位置来动态地聚焦于问题的特定部分,从而在保持算法效率的同时减少不必要的重复计算。在解决这类问题时,滑动窗口不仅能够提供优化的解决方案,还能帮助理解和分析数据的连续性质。

回到题目

根据我的理解,其实滑动窗口的核心思想

  • 就是把已经遍历过的内容存储在窗口里,这样对于下一次的遍历能够重复使用,减少再次遍历的开销。

而如果我们明确了使用滑动窗口来解决题目,那么我们就需要从以下几点着手:

  1. 窗口的大小:我们想把窗口指定多大比较合适?

  2. 窗口的移动:窗口可以向前“滑动”,每次移动可以是一步也可以是多步,这取决于问题的具体要求。窗口的移动使得算法能够逐步遍历整个数据集。我们应该怎么设置窗口的移动规则?

  3. 数据的复用:当窗口移动时,一些数据会从窗口中移出,同时会有新的数据加入到窗口中。窗口内的这些数据可以被复用来计算新的结果,从而避免了对已经遍历过的数据进行重复的计算。那我们怎么在这个问题中复用数据?

  4. 动态调整:窗口的大小是否需要动态调整?对于某些问题,窗口的大小可以根据特定的条件动态调整,比如在寻找满足条件的最小子序列长度时。这种动态调整能够帮助算法更加灵活地应对不同的问题需求。

根据上面几个点,我们可以一一来回答,但首先我们先回过头看看暴力解法为什么那么慢?

原因就是我每一次从一个字符开始,明明后面的很多内容遍历过了,但是在第二次for循环时我们还需要从第二个字符开始,重新走之前走的内容。因此我们就可以想一想是不是就可以指定一个窗口,用来容纳那些已经走过的地方,等到下一次遍历,我就直接使用这个窗口的数据。

但是这个窗口存什么呢?

窗口中存储的就是我们上一次for循环走过的尝试与words中内容进行匹配的数据,匹配不成功自然是从下一个位置开始,但是如果匹配成功了,那么下一次遍历我们就可以不需要再次匹配窗口中的数据

因此就可以回答上面提出的几点问题了:窗口大小动态变化,窗口的移动一次移动一个words[i]的长度,但是这样还不够,因为如果每次跳过words[i].length个字符的话,我们对于每一个words[i]长度内部的起始位置我们会忽视掉,因为正如前几篇滑动窗口讲得一样,虽然滑动窗口很高效,但是它并没有偷懒,也就是它并没有忽视对每个位置的判断,只是将判断的过程简化了。如果我们以words[i]的长度为步长,会得到下图:

就是一个一个红色的框,但是我们忽视了如下紫色和绿色的框的起始位置的判断:

但是幸运的是,只需要words[i]个长度的框,就会出现重复的框,如下:

虽然可能解释起来用话说并不是特别清晰,但是通过图片我想大家应该知道是什么意思。因此我们的窗口就可以分为words[i].length类,比如 words = ["ab","cd","ef"],因为words[i].length = 2,所以定义2个窗口,就可以覆盖所有的范围。

接下来我们来考虑窗口如何利用数据:

如上图所示,对于字符串S遍历过程中,指定三个窗口,如果能够匹配成功words中的某一个单词,就扩充窗口,这样在下一次遍历到窗口一类型的起始点的时候,如上紫色框所示内容就已经知道是能够匹配成功的,就无需再进行匹配,只需要判断黄色框是否能匹配即可。

因此我们基本可以得到如下的代码思路:(定义 words[i].length = n

  1. 初始化,定义 n 个窗口,同时定义 n 个hashMap,用来存储words中的单词及其出现的个数(也可以放在每一次的外层for循环中)

  2. 外层for循环遍历窗口的个数(n个)

  3. 内层循环遍历不同的开头,比如对于窗口一,其遍历起始位置集合为:{ 0, 0 + n, 0 + 2n ...... }。移动右指针,每次加入一个单词,对应的一个记录窗口内部的单词计数的hashMap对应位置也加一。

    • 如果当前单词对应窗口内部计数开始大于 存储words中的单词及其出现的个数,说明已经出现匹配不成功的情况了,因此就需要移动左指针,直到删除这个单词。

    • 如果窗口内单词的出现次数,也就是 right-left的长度等于 words 中的单词的总长,说明找到了一个解。因为我们先对窗口内部的单词进行了计数,如果大于存储words中的单词及其出现的个数是会移动左指针的,而当任意一个窗口内部的单词的数量小于存储words中的单词数量,那长度肯定是不匹配的,所以只有窗口内部每一个的单词的数量完全匹配words中的单词数量,也就是 right-left的长度等于 words 中的单词的总长,说明匹配成功!

3. 代码实现

3.1 暴力求解

运行结果如上所示会超时!

3.2 滑动窗口

4. 相关复杂度分析

为了分析这两种解法的时间和空间复杂度,我们假定一些基本参数:

  • 假设字符串s的长度为N

  • 假设单词数组words包含M个单词,每个单词的长度为L

  • 因此,所有单词串联形成的字符串长度是M*L

4.1 暴力解法的复杂度分析

时间复杂度

  • 对于字符串s中的每个字符,算法尝试匹配所有单词串联形成的子串。

  • 对于每个起始位置,算法最坏情况下需要比较M*L长度的字符串。

  • 因此,最坏情况下的时间复杂度是O(N*M*L)

空间复杂度

  • 需要一个HashMap来存储words中单词及其出现的次数,其空间复杂度为O(M)

  • 每次循环时,都会创建一个wordsAndCount的副本,因此空间复杂度保持为O(M)

4.2 滑动窗口解法的复杂度分析

时间复杂度

  • 由于窗口的滑动是线性的,并且每个字符最多被访问两次(一次加入窗口,一次从窗口移除),这个复杂度可以优化为O(N)

空间复杂度

  • 使用了两个HashMap来存储words中单词及其出现次数以及当前窗口内单词及其出现次数,空间复杂度为O(M)

4.3 总结

  • 暴力解法的时间复杂度较高,为O(N*M*L),空间复杂度为O(M)

  • 滑动窗口解法通过优化遍历过程,将时间复杂度降低到O(N),空间复杂度保持为O(M)

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Hive拉链表设计、实现、总结

水善利万物而不争,处众人之所恶,故几于道💦 文章目录 环境介绍实现1. 初始化拉链表2. 后续拉链表数据的更新 总结彩蛋 - 想清空表的数据:转成内部表,清空数据后,再转成外部表,将分区目录删掉&am…

无心剑英译仓央嘉措《永在我心》

永在我心 Forever in My Heart 仓央嘉措 By Tsangyang Gyatso 这么多年 你一直在我心口幽居 我放下过天地 放下过万物 却从未放下过你 so many years slipped away you’ve been living in my heart I’ve dropped heaven and earth even dropped everything but never dr…

OWASP TOP10

OWASP TOP10 OWASP网址:http://ww.owasp.org.cn A01:失效的访问控制 例如:越权漏洞 案例1: 正常:每个人登录教务系统,只能查询自己的成绩信息 漏洞:张三登录后可以查看自己的成绩 例如&…

人工智能学习与实训笔记(五):神经网络之推荐系统处理

目录 ​​​​​​​七、智能推荐系统处理 7.1 常用的推荐系统算法 7.2 如何实现推荐​​​​​​​ 7.3 基于飞桨实现的电影推荐模型 7.3.1 电影数据类型 7.3.2 数据处理 7.3.4 数据读取器 7.3.4 网络构建 7.3.4.1用户特征提取 7.3.4.2 电影特征提取 7.3.4.3 相似度…

智能网卡(SmartNIC):增强网络性能

在当今的数字时代,网络性能和数据安全是各行各业面临的关键挑战。智能网卡是一项颠覆性的技术创新,对增强网络性能和加强数据安全性具有关键推动作用。本文旨在探讨智能网卡的工作原理及其在不同应用场景中的重要作用。 什么是智能网卡? 智…

Rust 基本环境安装

rust 基本介绍请看上一篇文章:rust 介绍 rustup 介绍 rustup 是 Rust 语言的安装器和版本管理工具。通过 rustup,可以轻松地安装 Rust 编译器(rustc)、标准库和文档。它也允许你切换不同的 Rust 版本或目标平台,以及…

太以假乱真了,大家小心

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…

.NET Core MongoDB数据仓储和工作单元模式封装

前言 上一章我们把系统所需要的MongoDB集合设计好了,这一章我们的主要任务是使用.NET Core应用程序连接MongoDB并且封装MongoDB数据仓储和工作单元模式,因为本章内容涵盖的有点多关于仓储和工作单元的使用就放到下一章节中讲解了。仓储模式(R…

SpringMVC速成(二)

文章目录 SpringMVC速成(二)1.SSM整合1.1 流程分析1.2 整合配置步骤1:创建Maven的web项目步骤2:添加依赖步骤3:创建项目包结构步骤4:创建SpringConfig配置类步骤5:创建JdbcConfig配置类步骤6:创建MybatisConfig配置类步骤7:创建jdbc.properti…

云计算基础-虚拟化概述

虚拟化概述 虚拟化是一种资源管理技术,能够将计算机的各种实体资源(如CPU、内存、磁盘空间、网络适配器等)予以抽象、转换后呈现出来并可供分割、组合为一个或多个逻辑上的资源。这种技术通过在计算机硬件上创建一个抽象层,将单台…

《UE5_C++多人TPS完整教程》学习笔记15 ——《P16 会话接口委托(Session Interface Delegates)》

本文为B站系列教学视频 《UE5_C多人TPS完整教程》 —— 《P16 会话接口委托(Session Interface Delegates)》 的学习笔记,该系列教学视频为 Udemy 课程 《Unreal Engine 5 C Multiplayer Shooter》 的中文字幕翻译版,UP主&#xf…

Matplotlib plt.scatter:从入门到精通,只需一篇文章!

Matplotlib plt.scatter:从入门到精通,只需一篇文章!🚀 利用Matplotlib进行数据可视化示例 🌵文章目录🌵 一、plt.scatter入门:轻松迈出第一步 👣二、进阶探索:plt.scatt…

大文件上传如何做断点续传?

文章目录 一、是什么分片上传断点续传 二、实现思路三、使用场景小结 参考文献 一、是什么 不管怎样简单的需求,在量级达到一定层次时,都会变得异常复杂 文件上传简单,文件变大就复杂 上传大文件时,以下几个变量会影响我们的用…

用HTML和CSS打造跨年烟花秀视觉盛宴

目录 一、程序代码 二、代码原理 三、运行效果 一、程序代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>跨年烟花秀</title><meta name"viewport" content"widthdevi…

poetry,一个好用的Python项目依赖管理库

🏷️个人主页:鼠鼠我捏,要死了捏的主页 🏷️付费专栏:Python专栏 🏷️个人学习笔记,若有缺误,欢迎评论区指正 前言 在 Python 开发领域,项目依赖管理是一个至关重要的问题。Python Poetry 是一个现代化的项目依赖管理工具,旨在简化 Python 项目的依赖管理和打包…

【JavaSE】数据类型和运算符

目录​​​​​​​ 前言 数据类型 1. 数据类型的分类 2. 基本数据类型 变量 1. 概叙 2. 整型变量 3. 字节型 & 短整型 & 长整型变量 4. 单 / 双精度浮点型变量 5. 字符型变量 6. 布尔型变量 类型转换 1. 自动类型转换(隐式) 2. 强制类型转换(显式) 补…

身份治理存在权限问题

身份治理正迅速成为 CISO 的首要考虑因素。二十年前&#xff0c;当萨班斯-奥克斯利法案(SoX) 和其他监管指令在互联网泡沫破灭后诞生时&#xff0c;身份治理要求就出现了。合规性控制&#xff0c;例如用户访问审查和有效管理员工访问生命周期的需要&#xff0c;是当时身份治理的…

OpenCV中的边缘检测技术及实现

介绍: 边缘检测是计算机视觉中非常重要的技术之一。它用于有效地识别图像中的边缘和轮廓&#xff0c;对于图像分析和目标检测任务至关重要。OpenCV提供了多种边缘检测技术的实现&#xff0c;本博客将介绍其中的两种常用方法&#xff1a;Canny边缘检测和Sobel边缘检测。 理论介…

JavaSE-02笔记【封装~this和static】

文章目录 1.封装&#xff08;掌握&#xff09;1.1 封装的理解1.2 不封装存在的问题1.3 怎么封装1.4 难点解惑1.5 练习 2. this 和 static2.1 this&#xff08;掌握&#xff09;2.1.1 this是什么2.1.2 this 在实例方法中使用2.1.3 this访问实例变量2.1.4 this扩展①2.1.5 this扩…

林浩然与杨凌芸的Java时光魔法:格式化历险记

林浩然与杨凌芸的Java时光魔法&#xff1a;格式化历险记 The Java Time Odyssey of Lin Haoran and Yang Lingyun: A Formatting Adventure 在编程世界的一隅&#xff0c;有一个名叫林浩然的程序员。他是个Java大侠&#xff0c;对代码世界的法则了如指掌&#xff0c;尤其擅长驾…