力扣题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 ListfindAnagrams(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 ListfindAnagrams(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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月21日 04时00分41秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
oracle比较强大的函数,SQL和ORACLE函数比较
2019-04-21
php把整数拆分成数组,数组拆分处理(整数时的处理),该怎么处理
2019-04-21
php红包平均分配,红包平均分配算法
2019-04-21
linux磁盘的命令是,linux磁盘相关的命令
2019-04-21
linux服务器 缓存,Linux服务器内存使用分析及内存缓存
2019-04-21
linux英文包安装教程视频,Linux源码包安装过程讲解
2019-04-21
linux 关闭rsync服务器,linux下配置rsync服务器和实时同步
2019-04-21
linux初始化TCP服务失败,深入Linux系统追踪TCP初始化
2019-04-21
linux下vi编辑器的命令大全,linux下VI编辑器命令大全(超级完整版)
2019-04-21
C语言极坐标转直角坐标,C语言实现直角坐标转换为极坐标的方法
2019-04-21
16F877A和24C02通信汇编语言,PIC16f877A读写24c02程序
2019-04-21