leetcode 438. 找到字符串中所有字母异位词(优质解法)
题解:
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> integerList=new ArrayList<>(); //用于记录最终答案
//将 s 和 p 字符串转换为字符数组,方便讨论
char []charS=s.toCharArray();
char []charP=p.toCharArray();
int pLength=p.length();
int sLength=s.length();
int []hash1=new int[26]; //用于记录 p 字符串中每个字符出现的个数
int []hash2=new int[26]; //用于记录讨论的子串中每个字符出现的个数
int count=0; //符合条件的字符个数
//将 p 字符串中的每一个字符出现的个数记录下来
for (int i=0;i<pLength;i++){
char c=charP[i];
hash1[c-'a']++;
}
for(int left=0,right=0;right<sLength;right++){
//记录 right 指针指向的字符
int in=charS[right]-'a';
hash2[in]++;
//判断当前记录的字符是否是有效字符
if(hash2[in]<=hash1[in]){
count++;
}
//判断当前讨论的子串长度是否超过 p 字符串的长度
if(right-left+1>pLength){
int out=charS[left]-'a';
//判断出窗口的字符是否是有效字符
if(hash2[out]<=hash1[out]){
count--;
}
hash2[out]--;
left++;
}
if(count==pLength){
integerList.add(left);
}
}
return integerList;
}
}
题解:
? ? ? ? 首先本题题意很清晰,不需要过多解释
? ? ? ? 在看到一个题时,可以先想一下它的暴力解法,本题我们可以遍历出所有的子串,然后判断子串和 p 字符串是否是异位词(是否由相同的字符串组成),然后取每个子串第一位字符的下标即可
? ? ? ? 我们首先要考虑一个问题,如何判断子串和 p 字符串是否是异位词(是否由相同的字符串组成),我们可以通过 hash 表,记录 p 字符串中每个字符出现的次数和子串中每个字符出现的次数,进行比对,我们便知道两个字符串是否由相同字符组成
? ? ? ? 对于示例1进行分析
????????输入: s = "cbaebabacd", p = "abc"
? ? ? ? 让 L 和 R 指针指向下标为 0 的位置(因为我们要遍历所有的子串,所以从下标 0 开始), hash1 表记录 p 字符串所包含的字符个数,count 变量记录当前子串有效字符的个数,a-1,b-1,c-1 ,将 R 指针指向的字符添加到 hash2 表中,key=c,value=1,由于 hash1 表中 c 字符对应的 value 值为 1,表示当前的 c 字符是有效字符 count+1,让 R 指针向右移
c????????b????????a????????e????????b????????a????????b????????a????????c????????d
L
R
? ? ? ? R 指针移动到当前位置时,子串的长度等于 p 字符串的长度,并且有效字符个数 count = 3 = p.length ,代表子串中的所有字符都是有效字符,所以当前的子串和 p 字符串就是异位词,记录当前 L 指针指向的下标
c????????b????????a????????e????????b????????a????????b????????a????????c????????d
L
? ? ? ? ? ? ? ? ? ? R
? ? ? ? 将 R 指针向右移动,此时子串的长度 right - left + 1 = 4 >?p.length,代表以 L 指针指向的字符为首的字符串已经遍历完毕,让 L 指针向右移动,并在 hash2 中将字符 b 对应的 value 值减 1 ,由于字符 c?对应的 value 值为 1 ,小于等于 hash1 中字符 b 对应的 value 值,所以字符 c 是关键字符,在将 L 指针移动以后,要将关键字符数量 count 减 1
????????此处涉及到一个问题,下一轮 R 指针需要回到 L 指针所在的位置从头开始遍历子串吗,答案是不需要,因为 R 指针到当前位置后才出现了长度不符合要求的子串,说明 R 指针和 L 指针之间的子串是符合长度要求的(不包括 R 指针指向的字符),所以将 R 指针移到 L 指针所在的位置,R 指针也会慢慢移动回来
c????????b????????a????????e????????b????????a????????b????????a????????c????????d
? ? ? ? ? L
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? R
? ? ? ??
????????
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!