力扣 438找到字符串中所有字母异位词

https://leetcode.cn/problems/find-all-anagrams-in-a-string/

题目描述

在这里插入图片描述

题目分析

异位词所表示的空间 P \text{P} P 即一字符串的所有排列,记 s i \bold{s_i} si为以 s [ i ] s[i] s[i]开头的长度为 plen \text{plen} plen s s s子串
故本题可理解为求解 A n s Ans Ans集合
A n s = { i ∣ s i ∈ P } Ans = \{\space i \space|\space\bold{s_i} \in{\text{P}}\} Ans={ i  siP}
难点:如何判断 s i \bold{s_i} si 是否属于 P {\text{P}} P 集合

题目解法

思路1:通过sort函数可唯一确定一异位词空间,如此可以判断 s i \bold{s_i} si 是否属于题目要求的解空间 P {\text{P}} P

关键伪代码如下

sort(p);
for(...){temp <= s(i, plen);sort(temp);if(temp == p) ans.push(i);
}

思路2:通过count的方法唯一表示解空间

可以通过异位词的元素种类与对应个数唯一表示一异位词空间

代码如下

vector<int> findAnagrams(string s, string p) {int slen = s.length(), plen = p.length();vector<int> ans;if(s.length() < p.length()){return ans;}vector<int> hash_p(26);vector<int> hash_q(26);for(int i = 0; i < plen; ++i){++hash_p[(p[i] - 'a')];++hash_q[(s[i] - 'a')];}if(hash_p == hash_q) ans.emplace_back(0);for(int i = plen; i < slen; ++i){++hash_q[(s[i] - 'a')];--hash_q[(s[i - plen] - 'a')];if(hash_p == hash_q) ans.emplace_back(i - plen + 1);}return ans;
}

总结

通过滑动窗口进行遍历,通过"hash"将字符串子串映射到异位词表示空间

每一个表示代表了一个异位词空间(一个字符串的所有元素的全排列)
广义上讲,以上方法都属于一种hash

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

LabVIEW提高开发效率技巧----采用并行任务提高性能

在复杂的LabVIEW开发项目中&#xff0c;合理利用并行任务可以显著提高系统的整体性能和响应速度。并行编程是一种强大的技术手段&#xff0c;尤其适用于实时控制、数据采集以及多任务处理等场景。LabVIEW的数据流编程模型天然支持并行任务的执行&#xff0c;结合多核处理器的硬…

Toon Dinosaurs 2 可爱卡通恐龙怪物模型带动画

剑龙、甲龙、厚头龙、副龙、二龙和腕龙使用(根运动)动画文件绘制人物。 动画: 空闲+随机空闲动画跳跃(跳跃、跌倒、落地)。 3攻击 2个被击中,1个死亡和1个起床动画。 咆哮 左转和右转。跑,跑,转身。 最近添加:向前走,转身走。 查看视频以观看动画! 近似三角形计数:…

读构建可扩展分布式系统:方法与实践10最终一致性

1. 最终一致性 1.1. 在一些应用领域&#xff0c;通常谈论的是银行和金融行业&#xff0c;最终一致性根本不合适 1.2. 事实上&#xff0c;最终一致性在银行业已经使用了很多年 1.2.1. 支票需要几天时间才能在你的账户上进行核对&#xff0c;而且你可以轻松地开出比账户余额多的…

网络基础,协议,OSI分层,TCP/IP模型

网络的产生是数据交流的必然趋势&#xff0c;计算机之间的独立的个体&#xff0c;想要进行数据交互&#xff0c;一开始是使用磁盘进行数据拷贝&#xff0c;可是这样的数据拷贝效率很低&#xff0c;于是网络交互便出现了&#xff1b; 1.网络是什么 网络&#xff0c;顾名思义是…

oracle数据库启动

文章目录 背景一、步骤1.登录oracle用户2.启动监听服务3.启动数据库 背景 oracle数据库启动 一、步骤 1.登录oracle用户 代码如下&#xff08;示例&#xff09;&#xff1a; su - oracle2.启动监听服务 代码如下&#xff08;示例&#xff09;&#xff1a; lsnrctl start成…

生信初学者教程(四):软件

文章目录 RRstudioLinux系统其他软件本书是使用R语言编写的教程,用户需要下载R和RStudio软件用于进行分析。 版权归生信学习者所有,禁止商业和盗版使用,侵权必究 R R语言是一种免费的统计计算和图形化编程语言,是一种用于数据分析和统计建模的强大工具。它具有丰富的统计…

C++11——lambda

lambda lambda的介绍lambda的使用lambda的细节->捕捉列表 lambda的介绍 lambda是匿名函数&#xff0c;再适合的场景去使用可以提高代码的可读性。 场景&#xff1a; 假设有一个Goods类需要进行按照价格、数量排序 class Goods {string name;size_t _price;//价格int num;/…

【IoTDB 线上小课 07】多类写入接口,快速易懂的“说明书”!

【IoTDB 视频小课】稳定更新中&#xff01;第七期来啦~ 关于 IoTDB&#xff0c;关于物联网&#xff0c;关于时序数据库&#xff0c;关于开源... 一个问题重点&#xff0c;3-5 分钟&#xff0c;我们讲给你听&#xff1a; 一条视频了解写入接口 了解我们的友友们&#xff0c;应该…

我的AI工具箱Tauri版-VideoClipMixingCut视频批量混剪

本教程基于自研的AI工具箱Tauri版进行VideoClipMixingCut视频批量混剪。 VideoClipMixingCut视频批量混剪 是自研AI工具箱Tauri版中的一款强大工具&#xff0c;专为自动化视频批量混剪设计。该模块通过将预设的解说文稿与视频素材进行自动拼接生成混剪视频&#xff0c;适合需要…

关于http的206状态码和416状态码的意义、断点续传以及CORS使用Access-Control-Allow-Origin来允许跨域请求

一、关于http的206状态码和416状态码的意义及断点续传 HTTP 2xx范围内的状态码表明客户端发送的请求已经被服务器接受并且被成功处理了,HTTP/1.1 206状态码表示客户端通过发送范围请求头Range抓取到了资源的部分数据&#xff0c;一般用来解决大文件下载问题&#xff0c;一般CDN…

小小扑克牌算法

1.定义一个扑克牌类Card&#xff1a; package democard; public class Card {public String suit;//表示花色public int rank;//表示牌点数Overridepublic String toString() {return "{"suit rank"}";}//实例方法&#xff0c;初始化牌的点数和花色public…

Xinstall助力App推广,下载自动绑定提升转化率

在App推广和运营的过程中&#xff0c;我们经常会遇到一些痛点。比如&#xff0c;用户下载App后需要手动进行一系列繁琐的操作才能完成注册和绑定&#xff0c;这不仅影响了用户体验&#xff0c;还降低了转化率。那么&#xff0c;有没有一种方法能够简化这个过程&#xff0c;提升…

Vue使用axios实现Ajax请求

1、什么是 axios 在实际开发过程中&#xff0c;浏览器通常需要和服务器端进行数据交互。而 Vue.js 并未提供与服务器端通信的接口。从 Vue.js 2.0 版本之后&#xff0c;官方推荐使用 axios 来实现 Ajax 请求。axios 是一个基于 promise 的 HTTP 客户端。 关于 promise 的介绍…

开源 AI 智能名片小程序:开启内容营销新境界

摘要&#xff1a;本文深入探讨了在当今数字化时代&#xff0c;内容营销的重要性以及如何实现让用户主动找你的最佳效果。通过引入开源 AI 智能名片小程序这一创新工具&#xff0c;阐述了其在明确目标用户群体、迎合用户需求痛点和打造风格特色方面的独特优势&#xff0c;为企业…

达梦数据库踩坑

提示&#xff1a;第一次接触达梦&#xff0c;是真的不好用&#xff0c;各种报错不提示详细信息&#xff0c;吐槽归吐槽&#xff0c;还是需要学习使用的。 前言 题主刚接触达梦数据库时&#xff0c;本来是想下载官网的连接工具进行数据库连接的&#xff0c;但是谁曾想&#xff…

sql中的union与union all区别

sql中的union与union all区别 1、 区别2、效率3、使用建议 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 1、 区别 union&#xff1a; 功能&#xff1a;合并多个查询结果集&#xff0c;并自动去除重复行。特点&#xff1a;结果集中不包含重…

linux如何对c++进行内存分析

linux如何对c进行内存分析 背景分析方法以及原理原理分析结果以及重点关注 背景 在工作中&#xff0c;我遇到一个问题&#xff0c;需要将c写的进程部署到MCU上。由于MCU上可用的RAM 非常有限&#xff0c;所以在部署时就需要考虑到使用内存大小。所以为了搞清楚&#xff0c;内存…

计算机网络29——Linux基本命令vim,gcc编译命令

1、创建新用户 2、给用户设置密码 3、切换到新用户 切换到root用户 4、删除用户 5、查看ip 6、ping 查看物理上两台主机是否联通 7、netstatus 8、nslookup 查看网址的地址 9、负载均衡与容灾备份 负载均衡&#xff1a;指将负载&#xff08;工作任务&#xff09;进行平衡、分…

STM32如何修改外部晶振频率和主频

对于STM32F10x系列的单片机&#xff0c;除了STM32F10x_CL单片机&#xff0c;其它的单片机一般外部晶振HSE的时钟频率都默认是8MHz。如果我们使用的外部晶振为12Mhz&#xff0c;那么可以把上图绿色标记改为:12000000 72MHz的主频8MHz的外部晶振HSE*倍频系数9。当然如果像上面把外…

什么是HTTP DDOS,如何防护

在当今高度互联的网络世界中&#xff0c;网络安全威胁日益严峻&#xff0c;其中HTTP DDoS&#xff08;Distributed Denial of Service&#xff0c;分布式拒绝服务&#xff09;攻击作为一种常见的网络攻击手段&#xff0c;给企业和个人用户带来了巨大的挑战。今天我们就来详细介…