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

server/2024/9/24 0:16:36/

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

题目描述:

        给定两个字符串 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/server/45144.html

相关文章

垃圾收集器

文章目录 概要几个重要的概念Serial收集器ParNew 收集器Parallel Scavenge收集器Serial Old收集器Parallel Old收集器CMS收集器CMS垃圾收集过程并发标记过程多标漏标CMS收集器的三个缺点 G1收集器垃圾回收细节参数设置运行过程优缺点 概要 垃圾回收算法分类两类&#xff0c;第…

android13 差分包制作命令

./out/host/linux-x86/bin/ota_from_target_files -v -iCode/SourceCode/android13/ntls/userdebug/hpg2_24-target_files-38.zip --block -p ./out/host/linux-x86 Code/SourceCode/android13/ntls/userdebug/hpg2_24-target_files-39.zip update_ud.zip 脚本命令行参数 命令…

富凡行是什么软件,来具体聊一聊它的详情,感兴趣的不要错过了

目前做网络项目的人很多&#xff0c;也就衍生出了很多的软件、项目、平台。接触过了很多的产品&#xff0c;感触颇深&#xff0c;确实市面上的东西差别都很大&#xff0c;有好的&#xff0c;有不好的。 我也是喜欢在网上做点副业&#xff0c;自己捣鼓一下&#xff0c;毕竟互联网…

Codeforces Round 948 (Div. 2) E. Tensor(思维题-交互)

题目 n(3<n<100)个点的有向图&#xff0c; 图的边的关系未知&#xff0c;但保证以下两点&#xff1a; 1. 只存在j->i&#xff08;i<j&#xff09;的边 2. 对于任意三个点i、j、k&#xff08;i<j<k&#xff09;&#xff0c;要么k可以到达i&#xff0c;要么…

渗透测试工具Cobalt strike-2.CS基础使用

三、结合metasploit,反弹shell 在kali中开启使用命令开启metasploit msfconsole ┌──(root㉿oldboy)-[~] └─# msfconsole --- msf6 > use exploit/multi/handler [*] Using configured payload generic/shell_reverse_tcp --- msf6 exploit(multi/handler) > show …

Stable Diffusion 3报告

报告链接&#xff1a;Stable Diffusion 3: Research Paper — Stability AI 文章目录 要点表现架构细节通过重新加权改善整流流量Scaling Rectified Flow Transformer Models灵活的文本编码器RF相关论文 引言 随着人工智能技术的飞速发展&#xff0c;文本到图像生成领域正经…

写代码之前一定要提前想好思路

就和写数学题目一样&#xff0c;在做题目之前要先把思路确立下来。可能是我早年做数学的时候老是着急做题目没怎么分析过题目&#xff0c;把这个习惯不自觉地代入了代码的写入当中。习惯的养成使得我即使明白了自己的问题也依然会不断的犯错&#xff0c;看来只有刻意地提醒自己…

【算法刷题day60】Leetcode:84. 柱状图中最大的矩形

文章目录 Leetcode 84. 柱状图中最大的矩形解题思路代码总结 草稿图网站 java的Deque Leetcode 84. 柱状图中最大的矩形 题目&#xff1a;84. 柱状图中最大的矩形 解析&#xff1a;代码随想录解析 解题思路 反方向接雨水。见上一篇文章 代码 class Solution {public int la…