LeetCode(32)串联所有单词的子串【滑动窗口】【困难】(含图解)

在这里插入图片描述

目录

    • 1.题目
    • 2.答案
    • 3.提交结果截图
    • 4.图解

链接: 串联所有单词的子串

1.题目

给定一个字符串 s 和一个字符串数组 words words 中所有字符串 长度相同

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef""abefcd""cdabef""cdefab""efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1:

输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2:

输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3:

输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]
解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示:

  • 1 <= s.length <= 10^4
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i]s 由小写英文字母组成

2.答案

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        int wordLength = words[0].length();
        int wordCount = words.length;
        for (int i = 0; i < wordLength; i++) {
            // 超出长度
            if (i + wordCount * wordLength > s.length()) {
                break;
            }
            // 初始化窗口
            Map<String, Integer> map = new HashMap<>();
            for (int j = 0; j < wordCount; j++) {
                String word = s.substring(i + j * wordLength, i + (j + 1) * wordLength);
                map.put(word, map.getOrDefault(word, 0) + 1);
            }
            // 筛掉原单词数组
            for (String word : words) {
                map.put(word, map.getOrDefault(word, 0) - 1);
                if (map.get(word) == 0) {
                    map.remove(word);
                }
            }
            // 滑动窗口
            for (int j = 0; i + j + wordCount * wordLength <= s.length(); j+=wordLength) {
                if (j != 0) {
                    String addWord = s.substring(i + j + wordLength * (wordCount - 1), i + j + wordLength * wordCount);
                    map.put(addWord, map.getOrDefault(addWord, 0) + 1);
                    if (map.get(addWord) == 0) {
                        map.remove(addWord);
                    }
                    String delWord = s.substring(i + j - wordLength, i + j);
                    map.put(delWord, map.getOrDefault(delWord, 0) - 1);
                    if (map.get(delWord) == 0) {
                        map.remove(delWord);
                    }
                }
                if (map.size() == 0) {
                    result.add(i + j);
                }
            }
        }
        return result;
    }
}

3.提交结果截图

在这里插入图片描述

4.图解

以如下测试用例举例说明:

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

首先,可以将字符串 s 按照单词长度进行划分,通过开头跳过字符长度的方式,可以分为以下三种划分方式。

在这里插入图片描述

以划分方式1举例,可以将所有单词总长度(单词数 * 单词长度)来作为一个窗口,从左往右滑动。

在这里插入图片描述

在这里插入图片描述

最终得到的 index=0index=9 就是我们的结果了。

整理完毕,完结撒花~ 🌻

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

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

相关文章

用css实现原生form中radio单选框和input输入框的hover样式以及聚焦focus的样式

一.问题描述&#xff1a;用css实现原生form中radio单选框和input的hover已经focus的样式 在实际的开发中&#xff0c;一般公司ui都会给效果图&#xff0c;比如单选按钮radio样式&#xff0c;input输入框hover的时候样式&#xff0c;以及focus的时候样式&#xff0c;等等&#…

电脑内存升级

ddr代兼容 自从DDR内存时代开启之后&#xff0c;只要满足内存的插槽规格相同(DDR3或DDR4或DDR5即为内存规格)这一条件&#xff0c;不同品牌、不同频率以及不同容量的茶品都可以一起使用&#xff0c;除了品牌和容量的影响之外&#xff0c;不同频率的搭配可能会造成性能方面的影…

“我,24岁,年薪20万”:选对了行业究竟多重要?

那些在职场上顺风顺水&#xff0c;按部就班拿到高薪的人都有什么特点&#xff1f; 今天的主人公Flee告诉我&#xff0c;是稳。 在她的故事里&#xff0c;我看到一个“别人家的姑娘”&#xff0c;是怎样在职场上稳步晋升&#xff0c;大学毕业仅2年&#xff0c;就拿到18.6K月薪&a…

opencv-直方图均衡化

直方图均衡化是一种用于增强图像对比度的图像处理技术。它通过调整图像的灰度级别分布&#xff0c;使得图像中各个灰度级别的像素分布更均匀&#xff0c;从而提高图像的对比度。 在OpenCV中&#xff0c;你可以使用cv2.equalizeHist()函数来进行直方图均衡化。 以下是一个简单…

Flutter开发实践:用一套代码构建多端精美应用

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;CSDN领军人物&#xff0c;全栈领域优质创作者✌&#xff0c;CSDN博客专家&#xff0c;阿里云社区专家博主&#xff0c;2023年6月CSDN上海赛道top4。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师…

四、文件包含漏洞

一、文件包含漏洞 解释&#xff1a;文件包含漏洞是一种注入型漏洞&#xff0c;其本质就是输入一段用户能够控制的脚本或者代码&#xff0c;并让服务端执行&#xff1b;其还能够使得服务器上的源代码被读取&#xff0c;在PHP里面我们把可重复使用的函数写入到单个文件中&#x…

厦门某智慧社区的智慧排水监测系统实施落地

厦门某智慧社区的智慧排水监测系统实施落地 智慧社区的排水系统是一种高度智能化、高效且环保的排水解决方案&#xff0c;它结合了自动化控制系统、计算机网络技术、传感监测技术以及环保理念等多个领域的知识。其主要作用是确保社区的排水系统能够高效、稳定、环保地运行&…

如何用CHAT分析网络流行语的构成特点及趋势?

问CHAT&#xff1a;请分析下网络流行语的构成特点及趋势 CHAT回复&#xff1a; 网络流行语的构成特点&#xff1a; 1. 新颖性&#xff1a;网络流行语象征着新潮的概念、思想和观点&#xff0c;它们新颖独特且易于传播。 2. 深入人心的设定&#xff1a;网络流行语通常是由大众…

基于Vue3的低代码开发平台——JNPF

目录 一、什么是Vue.js &#xff1f; 二、Jnpf-Web-Vue3 的技术栈介绍 &#xff08;1&#xff09;Vue3.x &#xff08;2&#xff09;Vue-router4.x &#xff08;3&#xff09;Vite4.x &#xff08;4&#xff09;Ant-Design-Vue3.x &#xff08;5&#xff09;TypeScript &#x…

这样写postman实现参数化,阿里p8都直呼牛逼

什么时候会用到参数化 比如&#xff1a;一个模块要用多组不同数据进行测试 验证业务的正确性 Login模块&#xff1a;正确的用户名&#xff0c;密码 成功&#xff1b;错误的用户名&#xff0c;正确的密码 失败 postman实现参数化 在实际的接口测试中&#xff0c;部分参数…

猫罐头多久喂一次?放心猫罐头品牌推荐

猫罐头是猫咪喜爱的食物之一&#xff0c;然而&#xff0c;正确的喂养方法也是非常重要的。不能随意给猫咪喂食猫罐头。 作为从业6年的宠物护理师来说&#xff0c;只买合适的&#xff0c;贵的不如好的&#xff0c;只要配方不出错营养跟得上&#xff0c;观察自家猫咪体质真的基本…

【Mysql】[Err] 1293 - Incorrect table definition;

基本情况 SQL文件描述 /* Navicat MySQL Data TransferSource Server : cm4生产-200 Source Server Version : 50725 Source Host : 192.168.1.200:3306 Source Database : db_wmsTarget Server Type : MYSQL Target Server Version : 50725 File…

采用connector-c++ 8.0操作数据库

1.下载最新的Connector https://dev.mysql.com/downloads/connector/cpp/&#xff0c;下载带debug的库。 解压缩到本地&#xff0c;本次使用的是带debug模式的connector库&#xff1a; 注&#xff1a;其中mysqlcppconn与mysqlcppconn8的区别是&#xff1a; 2.在cmakelist…

面试官:什么是三色标记

程序员的公众号&#xff1a;源1024&#xff0c;获取更多资料&#xff0c;无加密无套路&#xff01; 最近整理了一波电子书籍资料&#xff0c;包含《Effective Java中文版 第2版》《深入JAVA虚拟机》&#xff0c;《重构改善既有代码设计》&#xff0c;《MySQL高性能-第3版》&…

14.(vue3.x+vite)组件间通信方式之pinia

前端技术社区总目录(订阅之前请先查看该博客) 示例效果 Pinia简介 Pinia 是 Vue 的存储库,它允许您跨组件/页面共享状态。 Pinia与Vuex比较 (1)Vue2和Vue3都支持,这让我们同时使用Vue2和Vue3的小伙伴都能很快上手。 (2)pinia中只有state、getter、action,抛弃了Vu…

产品经理的具体工作职责有什么?

产品经理是现代企业中非常重要的一种职位&#xff0c;其工作职责也非常广泛和复杂。产品经理需要在市场、用户、技术等多个方面进行综合考虑&#xff0c;为企业开发出具有竞争力的产品&#xff0c;从而推动企业的发展。下面我们将详细介绍产品经理的具体工作职责。 一、市场调研…

第二十章 多线程

20.2创建线程 20.2.1继承Thread类 Thread类是Java.lang包中的一个类&#xff0c;从这个类中实例化的对象代表线程&#xff0c;程序员启动一个新线程需要建议Thread实例。 public class ThreadTest extedns Thread{} run方法格式&#xff1a; public void run(){} 20.1让线…

opencv-2D直方图

cv2.calcHist() 是 OpenCV 中用于计算直方图的函数。它可以计算一维或多维直方图&#xff0c;用于分析图像中像素值的分布。 基本的语法如下&#xff1a; hist cv2.calcHist(images, channels, mask, histSize, ranges[, hist[, accumulate]])参数说明&#xff1a; images:…

Verilog开源项目——百兆以太网交换机(三)Hash模块设计

Verilog开源项目——百兆以太网交换机&#xff08;三&#xff09;Hash模块设计 &#x1f508;声明&#xff1a;未经作者允许&#xff0c;禁止转载 &#x1f603;博主主页&#xff1a;王_嘻嘻的CSDN主页 &#x1f511;全新原创以太网交换机项目&#xff0c;Blog内容将聚焦整体架…

TypeScript 学习笔记 第二部分 webpack 创建typescript项目

【视频链接】尚硅谷TypeScript教程&#xff08;李立超老师TS新课&#xff09; 创建webpack 项目 IDE&#xff1a;webstorm 新建一个空的项目运行npm init初始化项目目录结构 1. 安装 webpack&#xff1a;构建工具webpack-cli&#xff1a; webpack的命令行工具typescript&am…