数据结构与算法:Find All Anagrams in a String

给出两个字符串s和p，当s中存在p的异构串时，返回所有s中对应的所有起点位置。

Example 1:

Input: s="cbaebabacd", p="abc"Output:[0,6]Explanation: The substring with start index=0is"cba",whichis an anagram of"abc".The substring with start index=6is"bac",whichis an anagram of"abc".

Example 2:

Input: s="abab", p="ab"Output:[0,1,2]Explanation: The substring with start index=0is"ab",whichis an anagram of"ab".The substring with start index=1is"ba",whichis an anagram of"ab".The substring with start index=2is"ab",whichis an anagram of"ab"

importjava.util.ArrayList;importjava.util.HashMap;importjava.util.List;importjava.util.Map;publicclassCode_FindAllAnagramsInAString{publicstaticList<Integer>findAnagrams(Strings,Stringp){List<Integer>ans=newArrayList<>();char[]str=s.toCharArray();char[]ptr=p.toCharArray();intM=p.length();Map<Character,Integer>map=newHashMap<>();intall=M;intN=str.length;if(M>N){returnans;}for(inti=0;i<M;i++){if(map.containsKey(ptr[i])){map.put(ptr[i],map.get(ptr[i])+1);}else{map.put(ptr[i],1);}}for(intend=0;end<M-1;end++){if(map.containsKey(str[end])){intcount=map.get(str[end]);if(count>0){all--;}map.put(str[end],count-1);}}// map表相当于一张欠表。 别人欠我多少。// 比如p字符串 abc. 那么map的数据是 a,1; b,1; c,1; 别人欠我1个// a, 欠1个b,欠1个c. all变量表示一共欠多少。for(intend=M-1,start=0;end<N;end++,start++){if(map.containsKey(str[end])){intcount=map.get(str[end]);if(count>0){all--;}map.put(str[end],count-1);}if(all==0){ans.add(start);}if(map.containsKey(str[start])){intcount=map.get(str[start]);if(count>=0){all++;}map.put(str[start],count+1);}}returnans;}}