串联所有单词的子串

题目链接

串联所有单词的子串

题目描述


注意点

  • 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;
    }
}

关键点

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

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

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

相关文章

K8s Pod资源管理组件

目录 Pod基础概念 在Kubrenetes集群中Pod有如下两种使用方式 pause容器使得Pod中的所有容器可以共享两种资源 网络 存储 总结 kubernetes中的pause容器主要为每个容器提供功能 Kubernetes设计这样的Pod概念和特殊组成结构的用意 通常把Pod分为以下几类 自主式Pod 控…

高温应用中GaN HEMT大信号建模的ASM-HEMT

来源&#xff1a;An ASM-HEMT for Large-Signal Modeling of GaN HEMTs in High-Temperature Applications&#xff08;JEDS 23年&#xff09; 摘要 本文报道了一种用于模拟高温环境下氮化镓高电子迁移率晶体管&#xff08;GaN HEMT&#xff09;的温度依赖性ASM-HEMT模型。我…

算法沉淀——动态规划之子序列问题(下)(leetcode真题剖析)

算法沉淀——动态规划之子序列问题 01.最长定差子序列02.最长的斐波那契子序列的长度03.最长等差数列04.等差数列划分 II - 子序列 01.最长定差子序列 题目链接&#xff1a;https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/ 给你一个整数数…

springboot+maven项目导入本地jar包,以有打包错误问题

1 本地jar包放置路径为&#xff1a; 2添加Modules File->project settings–>Modules–>Dependencies–>–>, 3 添加 Libraies 至此 项目即可成功运行。 mvn 打包错误&#xff0c;需要 运行以下命令 mvn install:install-file -Dfile${project.basedir}/s…

Python进阶学习:Numpy--ndim、shape、dtype、astype的用法说明

Python进阶学习&#xff1a;Numpy–ndim、shape、dtype、astype的用法说明 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1f448…

拥有美国洛杉矶RAKsmart云服务器:探索无限可能

随着信息技术的飞速发展&#xff0c;云服务器已成为企业和个人用户不可或缺的重要工具。美国洛杉矶的RAKsmart云服务器&#xff0c;凭借其卓越的性能、稳定的网络环境和高级的安全性&#xff0c;为用户提供了无尽的便利和可能性。那么&#xff0c;拥有这样一台云服务器&#xf…

【Java程序设计】【C00338】基于Springboot的银行客户管理系统(有论文)

基于Springboot的银行客户管理系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的银行客户管理系统&#xff0c;本系统有管理员、员工以及用户二种角色&#xff1b; 管理员&#xff1a;个人中心、管理员管理、客…

LabVIEW水下温盐深数据一体化采集与分析

LabVIEW水下温盐深数据一体化采集与分析 开发一个基于LabVIEW的水下温盐深数据一体化采集与分析系统&#xff0c;实现海洋环境监测的自动化和精确化。通过集成温度、盐度和深度传感器&#xff0c;结合USB数据采集卡&#xff0c;利用LabVIEW软件开发的图形化界面&#xff0c;实…

Java Web(十一)--JSON Ajax

JSON JSon在线文档&#xff1a; JSON 简介 JSON(JavaScript Object Notation, JS 对象标记) 是一种轻量级的数据交换格式。轻量级指的是跟xml做比较。数据交换指的是客户端和服务器之间业务数据的传递格式。 它基于 ECMAScript (W3C制定的JS规范)的一个子集&#xff0c;采…

10-Linux部署ElasticSearch

Linux部署ElasticSearch 简介 全文搜索属于最常见的需求&#xff0c;开源的 Elasticsearch &#xff08;以下简称 es&#xff09;是目前全文搜索引擎的首选。 它可以快速地储存、搜索和分析海量数据。维基百科、Stack Overflow、Github 都采用它。 Elasticsearch简称es&…

使用HTML5画布(Canvas)模拟图层(Layers)效果

使用HTML5画布&#xff08;Canvas&#xff09;模拟图层&#xff08;Layers&#xff09;效果 在图形处理和计算机图形学中&#xff0c;图层&#xff08;Layers&#xff09;是指将图像分成不同的可独立编辑、组合和控制的部分的技术或概念。每个图层都可以包含不同的图形元素、效…

亚马逊云科技实时 AI 编程助手 Amazon CodeWhisperer,开发快人一步

​ ​ Amazon CodeWhisperer 是一款 AI 编码配套应用程序&#xff0c;可在 IDE 中生成 整行代码和完整的函数代码建议&#xff0c;以帮助您更快地完成更多工作。在本系列 文章中&#xff0c;我们将为您详细介绍 Amazon CodeWhisperer 的相关信息&#xff0c;敬请 关注&#xff…

spring boot 修复 Spring Framework URL解析不当漏洞(CVE-2024-22243)

漏洞描述 当应用程序使用UriComponentsBuilder来解析外部提供的URL&#xff08;如通过查询参数&#xff09;并对解析的URL的主机执行验证检查时可能容易受到Open重定向攻击和SSRF攻击&#xff0c;导致网络钓鱼和内部网络探测等。 受影响产品或系统 6.1.0 < Spring Framew…

改进的yolo交通标志tt100k数据集目标检测(代码+原理+毕设可用)

YOLO TT100K: 基于YOLO训练的交通标志检测模型 在原始代码基础上&#xff1a; 修改数据加载类&#xff0c;支持CoCo格式&#xff08;使用cocoapi&#xff09;&#xff1b;修改数据增强&#xff1b;validation增加mAP计算&#xff1b;修改anchor&#xff1b; 注: 实验开启weig…

Spring Boot项目中如何上传头像?

在我们常见的各大App中&#xff0c;或多或少我们都见过上传头像的功能吧&#xff1f;&#xff1f; 但是在Spring Boot项目中如何上传头像呢&#xff1f; 上传头像主要用到RequestPart注解 来看一下小编的代码吧&#xff01; RestController RequestMapping("/param"…

嵌入式烧录报错:板端IP与PC的IP相同

报错&#xff1a; 配置 实际上我配置并没有错。 服务器IP&#xff08;就是本机&#xff09;、板端IP、网关。此处网关必须与板子IP配套&#xff08;可以不存在&#xff09;。 解决 我网卡配置了多个IP。一番删除添加还是报错。 于是点击服务器IP&#xff0c;换成别的&#x…

基于redis实现【最热搜索】和【最近搜索】功能

目录 一、前言二、分析问题三、针对两个问题&#xff0c;使用redis怎么解决问题&#xff1f;1、字符串String2、列表List3、字典Hash4、集合Set5、有序集合ZSet6、需要解决的五大问题 四、编写代码1.pom依赖2.application.yml配置3.Product商品实体4.用户最近搜索信息5.redis辅…

TCP缓存

TCP缓存是指TCP协议在数据传输过程中使用的一种机制&#xff0c;用于临时存储和管理数据包。它主要有三个作用&#xff1a;提高网络性能、保证数据的可靠性和实现流量控制。 首先&#xff0c;TCP缓存可以提高网络性能。当发送端发送数据时&#xff0c;TCP协议会将数据分割成若…

从Spring Boot应用上下文获取Bean定义及理解其来源

前言 在Spring框架中&#xff0c;Bean是组成应用程序的核心单元。特别是在Spring Boot项目中&#xff0c;通过使用SpringApplication.run()方法启动应用后&#xff0c;我们可以获得一个ConfigurableApplicationContext实例&#xff0c;这个实例代表了整个应用程序的运行时环境…

golang使用gorm操作mysql1

1.mysql连接配置 package daoimport ("fmt""gorm.io/driver/mysql""gorm.io/gorm""gorm.io/gorm/logger" )var DB *gorm.DB// 连接数据库&#xff0c;启动服务的时候&#xff0c;init方法就会执行 func init() {username : "roo…