Find All Anagrams in a String
给两个字符串s和p, 找出p在s中所有的anagram.
但凡是anagram基本都是用counting, 这个题也是, 因为已知p的长度, 所以用两个指针即可扫描所有可能的substring, 然后找出anagram即可, 找anagram用hash.
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int[] count = new int[26];
List<Integer> res = new ArrayList<>();
for(char c : p.toCharArray())
count[c - 'a']++;
int h = hash(count);
int[] count_s = new int[26];
int n = p.length();
for(int i = 0; i < s.length(); i++) {
if(i > n - 1)
count_s[s.charAt(i - n) - 'a']--;
count_s[s.charAt(i) - 'a']++;
if(h == hash(count_s))
res.add(i-n+1);
}
return res;
}
public int hash(int[] nums) {
int h = 0;
int p = 31;
int mod = 100001;
for(int i = 0; i < nums.length; i++) {
h += ((h * p) + nums[i]) % mod;
}
return h;
}
}