力扣题438找到字符串中所有字母异位词
发布日期:2022-03-04 11:48:19 浏览次数:4 分类:技术文章

本文共 2589 字,大约阅读时间需要 8 分钟。

给定两个字符串 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" 的异位词。
 

提示:

1 <= s.length, p.length <= 3 * 104

s 和 p 仅包含小写字母

1.自己的解法:用一个辅助数组计算p中各个字符出现的次数,然后用一个滑动窗口向右移,然后判断每个滑动窗口内的字符是否符合要求,如果符合的话,窗口的起点下标就加入队列。

class Solution {    public List
findAnagrams(String s, String p) { List
list = new ArrayList<>(); int sLength = s.length(); int pLength = p.length(); if (sLength < pLength) {//如果s的长度小于p的长度,肯定不存在了 return list; } int[] counts = new int[26];//存储p中每个字符出现的次数 for (int i= 0;i < pLength;i++) { counts[p.charAt(i) - 'a']++; } for (int i = 0;i <= s.length() - p.length();i++) {//遍历滑动窗口 //因为数组要重复使用,所以先复制一份 int[] countsOfCopy = Arrays.copyOf(counts,counts.length); if (isAnagrams(s,countsOfCopy,i,pLength)) {//遇到符合的窗口就将起始下标加入对垒 list.add(i); } } return list; } public boolean isAnagrams(String s,int[] countsOfCopy,int index,int pLength) { for (int i = index;i < index + pLength;i++) { countsOfCopy[s.charAt(i) - 'a']--; //如果出现字符出现数量小于0的情况,说明当前窗口肯定不符合要求,直接返回false if (countsOfCopy[s.charAt(i) - 'a'] < 0) { return false; } } return true;//说明情况都符合要求,返回true }}

2.对滑动窗口进行优化:来自评论@Edward Elric。

        变长窗口,用一个low和high来存储一个滑动窗口,如果当前遍历到的字符存在于p中,那么

      就把high右移,如果不存在,就需要右移low,但是要注意把之前减掉的数量还原回来,即补充

      消耗的字符。

class Solution {    public List
findAnagrams(String s, String p) { List
list = new ArrayList<>(); int[] counts = new int[26]; for (int i = 0;i < p.length();i++) {//统计p中每个字符出现的次数 counts[p.charAt(i) - 'a']++; } int low = 0;//滑动窗口的左下标 int high = 0;//滑动窗口的右下标 while (high < s.length()) { if (counts[s.charAt(high) - 'a'] > 0) {//如果当前遍历到的字符是p中存在的 counts[s.charAt(high) - 'a']--;//将出现数量见减1 high++;//右移滑动窗口的右下标 if (high - low == p.length()) {//如果窗口大小就是p的长度,说明找到了 list.add(low); } } else {//如果当前遍历到的字符是p中不存在的 counts[s.charAt(low) - 'a']++;//要恢复之前消耗的字符数量, low++;//右移滑动窗口的下标 } } return list; }}

题源:

转载地址:https://blog.csdn.net/xxyneymar/article/details/122268785 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:力扣题448找到所有数组中消失的数字
下一篇:力扣题312戳气球

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月21日 04时00分41秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

oracle比较强大的函数,SQL和ORACLE函数比较 2019-04-21
oracle12c order by,oracle 数据库中order by 的一些高级用法 2019-04-21
oracle8i substr,Oracle中的INSTR,NVL和SUBSTR函数的用法详解 2019-04-21
导出oracle11g的空表,轻松解决oracle11g 空表不能 exp 导出 的问题。 2019-04-21
php把整数拆分成数组,数组拆分处理(整数时的处理),该怎么处理 2019-04-21
oracle numlist,oracle sql str2numlist numtabletype 2019-04-21
php红包平均分配,红包平均分配算法 2019-04-21
linux磁盘的命令是,linux磁盘相关的命令 2019-04-21
linux服务器 缓存,Linux服务器内存使用分析及内存缓存 2019-04-21
linux查进程内存问题,关于linux 查看服务进程内存,cpu,内存占用的一些基础命令... 2019-04-21
linux英文包安装教程视频,Linux源码包安装过程讲解 2019-04-21
linux 关闭rsync服务器,linux下配置rsync服务器和实时同步 2019-04-21
linux初始化TCP服务失败,深入Linux系统追踪TCP初始化 2019-04-21
arch Linux添加源,在Arch Linux系统中使用Archlinuxcn源(清华源)的方法 2019-04-21
私人linux远程连接,Linux远程连接 - osc_5g1gl9wp的个人空间 - OSCHINA - 中文开源技术交流社区... 2019-04-21
windows文件迁移到linux,从Windows到Linux迁移之文件服务器(Samba和AD完美结合) 2019-04-21
linux下vi编辑器的命令大全,linux下VI编辑器命令大全(超级完整版) 2019-04-21
linux结构体数组的定义数组,task_struct结构体中的run_list和array域 2019-04-21
C语言极坐标转直角坐标,C语言实现直角坐标转换为极坐标的方法 2019-04-21
16F877A和24C02通信汇编语言,PIC16f877A读写24c02程序 2019-04-21