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;
    }
}