【LeetCode】438.找到字符串中所有字母异位词

ops/2024/9/22 22:54:31/

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

题目描述:

        给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

思路分析:

依然是滑动窗口法

        根据题目要求,我们需要在字符串 s寻找字符串 p 的异位词。因为字符串 p 的异位词的长度一定与字符串 p的长度相同,所以我们可以在字符串 s中构造一个长度为与字符串 p 的长度相同的滑动窗口,并在滑动中维护窗口中每种字母的数量;当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时,则说明当前窗口为字符串 p 的异位词。

优化思路

        在上述方法的基础上,我们不再分别统计滑动窗口和字符串中每种字母的数量,而是统计滑动窗口和字符串 p中每种字母数量的差;并引入变量cnt来记录当前窗口与字符串 p中数量不同的字母的个数,并在滑动窗口的过程中维护它。

        在判断滑动窗口中每种字母的数量与字符串 p中每种字母的数量是否相同时,只需要判断cnt是否为零即可。

代码实现注解:

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer>res=new ArrayList<>();//定义一个一维数组记录字母在两个字符串中出现的差值//cnt[x] = 0  表示 s与p中字母x出现次数相同 都出现了n次//cnt[x] = n  表示 在s中字母x出现次数比p多 多出现了n次//cnt[x] = -n 表示 在s中字母x出现次数比p少 少出现了n次int[]cnt=new int[26];//统计字符数量int n=p.length();int m=s.length();//如果目标字符长度大于原始字符长度,返回空数组if(n>m){return res;}//开始遍历数组,创造窗口滑块,p数组出现的字母数值加一,S数组出现的字母数字减一。//所以当cnt数组上的数值为0是代表在滑块中p和s出现该字母的频率一致for(int i=0;i<n-1;i++){cnt[p.charAt(i)-'a']++;cnt[s.charAt(i)-'a']--;}//将P字符串中的最后一个字母读入cnt中cnt[p.charAt(n-1)-'a']++;int l=0;//将S字符串中的n-1位置上的字母作为滑块的右边界//开始滑动窗口for(int r=n-1;r<m;r++){cnt[s.charAt(r)-'a']--;int o=0;//随着右边界的右移,判断新的右边界。如果cnt数组上的数值为0,那么o赋值为1for(int j=0;j<26;j++){o+=cnt[j]==0?1:0;}//说明s和p的同一个字母出现频率相等if(o==26){res.add(l);}//左边界向右移,缩小窗口cnt[s.charAt(l++)-'a']++;}return res;}
}


http://www.ppmy.cn/ops/44838.html

相关文章

包和final

一.什么是包&#xff1f; 包就是文件夹,用来管理各种不同功能的Java类,方便后期代码维护。 二.包名的规则 公司域名反写包的作用,需要全部英文小写&#xff0c;见名知意。 com.xxx.domain domain:这个包是干什么的。 三.使用其他类的规则 1.使用同一个包中的类时,不需要导…

vmware中Ubuntu虚拟机和本地电脑Win10互相ping通

初始状态 使用vmware17版本安装的Ubuntu的20版本&#xff0c;安装之后什么配置都要不懂&#xff0c;然后进行下述配置。 初始的时候是NAT&#xff0c;没动的. 设置 点击右键编辑“属性” 常规选择“启用”&#xff1a; 高级选择全部&#xff1a; 打开网络配置&#xff0c;右键属…

数据库设计实例---学习数据库最重要的应用之一

一、引言【可忽略】 在学习“数据库系统概述”这门课程时&#xff0c;我一直很好奇&#xff0c;这样一门必修课&#xff0c;究竟教会了我什么呢&#xff1f; 由于下课后&#xff0c;&#xff0c;没有拓展自己的眼界&#xff0c;上课时又局限于课堂上老师的讲课水平&#xff0c;…

风萧萧兮易水寒,壮士一去兮不复还 的 rm 命令

风萧萧兮易水寒&#xff0c;壮士一去兮不复还 的 rm 命令 风萧萧兮易水寒&#xff0c;壮士一去兮不复还 的 rm语法几个示例/bin/rm Argument list too long – Linux”配合find与xargs完成删除海量文件使用find的delete选项 快速删除大文件 风萧萧兮易水寒&#xff0c;壮士一去…

【数据结构】探索树中的奇妙世界

专栏介绍&#xff1a; 哈喽大家好&#xff0c;我是野生的编程萌新&#xff0c;首先感谢大家的观看。数据结构的学习者大多有这样的想法&#xff1a;数据结构很重要&#xff0c;一定要学好&#xff0c;但数据结构比较抽象&#xff0c;有些算法理解起来很困难&#xff0c;学的很累…

el-pagination在删除非第一页的最后一条数据遇到的问题

文章目录 前言一、问题展示二、解决方案三、源码解析1、elementui2、elementplus 总结 前言 这个问题是element-ui中的问题&#xff0c;可以从源码中看出来&#xff0c;虽然页码更新了&#xff0c;active也是对的&#xff0c;但是未调用current-change的方法&#xff0c;这里就…

2024广东省赛 G.Menji 和 gcd

题目 #include <bits/stdc.h> using namespace std; #define int long long #define pb push_back #define fi first #define se second #define lson p << 1 #define rson p << 1 | 1 #define ll long long const int maxn 1e6 5, inf 1e12, maxm 4e4 …

为什么国际顶级黑客大都没学过计算机专业,而是自学成才?

相比于其他专业, 计算机确实是学习成本最小的一个专业了。 起步只需要一台电脑, 剩下的只要有网络, 那资源可以说就是无限的。软件、教材、算法。。还有什么是网上找不到的?但是话说回来, 大部分人都做不到这一点, 所以光看着媒体聚光灯下的那几个大神对一般人没有任何指导意…