当前位置: 首页 > 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…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...