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

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

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

给定一个字符串 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 <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

哈希表+滑动窗口

class Solution:def findSubstring(self, s: str, words: List[str]) -> List[int]:word_len = len(words[0])word_counter = Counter(words)s_len = len(s)if s_len < word_len * len(words):return []if s_len == word_len and s == words[0]:return [0]res = []for i in range(word_len):tmp_counter = word_counter.copy()left = right = iwhile left <= right < s_len:right_word = s[right:right+word_len]left_word = s[left:left+word_len]if right_word in word_counter:if tmp_counter[right_word] > 0:tmp_counter[right_word] -= 1if tmp_counter.total() == 0:res.append(left)else:tmp_counter[left_word] += 1left += word_lencontinueelse:tmp_counter = word_counter.copy()left = right + word_lenright += word_lenreturn res

滑动窗口固定写法

  1. while left <= right < s_len
  2. 正常情况右指针右滑 right += word_len 扩张
  3. 异常情况左指针右滑 left += word_len;continue 收缩
  4. 毛毛虫解法

小优化,使用 tmp_total 代替 tmp_counter.total(),好像没提升

class Solution:def findSubstring(self, s: str, words: List[str]) -> List[int]:word_len = len(words[0])word_counter = Counter(words)word_total = len(words)s_len = len(s)if s_len < word_len * len(words):return []if s_len == word_len and s == words[0]:return [0]res = []for i in range(word_len):tmp_counter, tmp_total = word_counter.copy(), word_totalleft = right = iwhile left <= right < s_len:right_word = s[right:right+word_len]left_word = s[left:left+word_len]if right_word in word_counter:if tmp_counter[right_word] > 0:tmp_counter[right_word] -= 1tmp_total -= 1if tmp_total == 0:res.append(left)else:tmp_counter[left_word] += 1tmp_total += 1left += word_lencontinueelse:tmp_counter = word_counter.copy()left = right + word_lentmp_total = word_totalright += word_lenreturn res

相关文章:

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

LeetCode 30. 串联所有单词的子串 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如&#xff0c;如果 words [“ab”,“cd”,“ef”]&#xff0c; 那么 “abcd…...

python本学期所有代码!

第一单元 ----------------------------------------------------------------------- #圆面积的计算 radius 25 area 3.1415 * radius * radius print(area) print("{:.2f}".format(area)) --------------------------------------------------------------------…...

武汉星起航:无锡跨境电商加速“出海”,物流升级助品牌全球布局

随着全球化的不断深入&#xff0c;跨境电商作为数字外贸的新业态&#xff0c;正逐渐成为无锡企业拓展海外市场的重要渠道。武汉星起航关注到&#xff0c;近年来&#xff0c;无锡市通过积极推进国际物流枢纽建设&#xff0c;完善海外仓布局&#xff0c;以及各特色产业带的积极参…...

Python+Pytest+Allure+Yaml+Pymysql+Jenkins+GitLab接口自动化测试框架详解

PythonPytestAllureYaml接口自动化测试框架详解 编撰人&#xff1a;CesareCheung 更新时间&#xff1a;2024.06.20 一、技术栈 PythonPytestAllureYamlJenkinsGitLab 版本要求&#xff1a;Python3.7.0,Pytest7.4.4,Allure2.18.1,PyYaml6.0 二、环境配置 安装python3.7&…...

stm32-hal库(5)--usart串口通信三种模式(主从通信)(关于通信失败和串口不断发送数据问题的解决)

问题&#xff1a; 最近发现&#xff0c;stm32cubemx最新版本f1系列的hal库&#xff08;1.85版本&#xff09;生成的hal库&#xff0c;其中stm32f1xx_hal_uart.c的库文件中&#xff0c;其串口发送接收存在一些问题&#xff1a; 1.没有使用 __HAL_LOCK 和 __HAL_UNLOCK 宏&…...

一文学会LVS:概念、架构、原理、搭建过程、常用命令及实战案例

引言 随着互联网技术的飞速发展&#xff0c;服务器负载均衡技术变得越来越重要。LVS&#xff08;Linux Virtual Server&#xff09;作为一种高效的负载均衡解决方案&#xff0c;广泛应用于各大企业的生产环境中。本文将深入探讨LVS的概念、架构、工作原理&#xff0c;详细讲解其…...

[Go 微服务] Kratos 使用的简单总结

文章目录 1.Kratos 简介2.传输协议3.日志4.错误处理5.配置管理6.wire 1.Kratos 简介 Kratos并不绑定于特定的基础设施&#xff0c;不限定于某种注册中心&#xff0c;或数据库ORM等&#xff0c;所以您可以十分轻松地将任意库集成进项目里&#xff0c;与Kratos共同运作。 API -&…...

【unity实战】使用旧输入系统Input Manager 写一个 2D 平台游戏玩家控制器——包括移动、跳跃、滑墙、蹬墙跳

最终效果 文章目录 最终效果素材下载人物环境 简单绘制环境角色移动跳跃视差和摄像机跟随效果奔跑动画切换跳跃动画&#xff0c;跳跃次数限制角色添加2d物理材质&#xff0c;防止角色粘在墙上如果角色移动时背景出现黑线条方法一方法二 墙壁滑行实现角色滑墙不可以通过移动离开…...

【实战】EasyExcel实现百万级数据导入导出

文章目录 前言技术积累实战演示实现思路模拟代码测试结果 前言 最近接到一个百万级excel数据导入导出的需求&#xff0c;大概就是我们在进行公众号API群发的时候&#xff0c;需要支持500w以上的openid进行群发&#xff0c;并且可以提供发送openid数据的导出功能。可能有的同学…...

Graalvm配置文件与Feature和Substitute机制介绍

GraalVM介绍 GraalVM提前将Java应用程序编译成独立与机器码二进制文件&#xff08;可执行文件、动态库文件&#xff09;,如windows系统中的exe文件和dll文件。与在Java虚拟机&#xff08;JVM&#xff09;上运行的应用程序相比&#xff0c;这些二进制文件更小&#xff0c;启动速…...

Appium adb 获取appActivity

方法一&#xff08;最简单有效的方法&#xff09; 通过cmd命令&#xff0c;前提是先打开手机中你要获取包名的APP adb devices -l 获取连接设备详细信息 adb shell dumpsys activity | grep mFocusedActivity 有时获取到的不是真实的Activity 方法二 adb shell monkey -p …...

调整分区失败致盘无法访问:深度解析与数据恢复全攻略

调整分区失败盘打不开的困境 在计算机的日常维护与管理中&#xff0c;调整磁盘分区是常见的操作之一&#xff0c;旨在优化存储空间布局、提升系统性能或满足特定应用需求。然而&#xff0c;当这一操作未能如预期般顺利进行&#xff0c;反而导致分区调整失败&#xff0c;进而使…...

试用笔记之-汇通计算机等级考试软件一级Windows

首先下载汇通计算机等级考试软件一级Windows http://www.htsoft.com.cn/download/htwork.rar...

Java的NIO体系

目录 NIO1、操作系统级别下的IO模型有哪些&#xff1f;2、Java语言下的IO模型有哪些&#xff1f;3、Java的NIO应用场景&#xff1f;相比于IO的优势在哪&#xff1f;4、Java的IO、NIO、AIO 操作文件读写5、NIO的核心类 :Buffer&#xff08;缓冲区&#xff09;、Channel&#xff…...

自下而上的选股与自上而下的选股

一起学习了《战胜华尔街》&#xff0c;不知道大家有没有这么一种感受&#xff1a;林奇的选股方法是典型的自下而上的选股方法。虽然这一点没有单独拎出来讨论过&#xff0c;但在《从低迷中寻找卓越》《如何通过财务指标筛选股票&#xff1f;》《边逛街边选股&#xff1f;》《好…...

Tech Talk:智能电视eMMC存储的五问五答

智能电视作为搭载操作系统的综合影音载体&#xff0c;以稳步扩大的市场规模走入越来越多的家庭&#xff0c;成为人们生活娱乐的重要组成部分。存储部件是智能电视不可或缺的组成部分&#xff0c;用于保存操作系统、应用程序、多媒体文件和用户数据等信息。智能电视使用eMMC作为…...

scikit-learn教程

scikit-learn&#xff08;通常简称为sklearn&#xff09;是Python中最受欢迎的机器学习库之一&#xff0c;它提供了各种监督和非监督学习算法的实现。下面是一个基本的教程&#xff0c;涵盖如何使用sklearn进行数据预处理、模型训练和评估。 1. 安装和导入包 首先确保安装了…...

CentOS 7 搭建rsyslog日志服务器

CentOS 7 搭建rsyslog日志服务器 前言一、IP地址及主机名称规划1.修改主机名 二、配置rsyslog日志服务器1.安装rsyslog服务2.编辑/etc/rsyslog.conf 文件3.启动并启用rsyslog服务4.验证端口是否侦听 三、在rsyslog日志服务器上配置firewalld防火墙四、配置rsyslog日志客户端1.编…...

使用Spring Boot Actuator监控应用健康状态

使用Spring Boot Actuator监控应用健康状态 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01;今天我们将探讨如何利用Spring Boot Actuator来监控和管理应用程序的…...

leetcode刷题:vector刷题

​ ​ &#x1f525;个人主页&#xff1a;guoguoqiang. &#x1f525;专栏&#xff1a;leetcode刷题 1.只出现一次的数字 这道题很简单&#xff0c;我们只需要遍历一次数组即可通过异或运算实现。(一个数与自身异或结果为0&#xff0c;任何数与0异或还是它本身) class Solut…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...