438. Find All Anagrams in a String(M)

https://leetcode.com/problems/find-all-anagrams-in-a-string/

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= s.length, p.length <= 3 * 104

• s and p consist of lowercase English letters.

Solution:

Version 1: (template solution)

呵呵，这个所谓的字母异位词，不就是排列吗，搞个高端的说法就能糊弄人了吗？相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。

直接默写一下框架，明确刚才讲的 4 个问题，即可秒杀这道题：

vector<int> findAnagrams(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    vector<int> res; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) 
                valid++;
        }
        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 当窗口符合条件时，把起始索引加入 res
            if (valid == need.size())
                res.push_back(left);
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return res;
}

跟寻找字符串的排列一样，只是找到一个合法异位词（排列）之后将起始索引加入 res 即可。

Version 2:

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        
        int len1 = s.length();
        int len2 = p.length();
        List<Integer> result = new ArrayList<>();
        if(len1<len2) return result;
        
        int[] count = new int[26];
        int[] windows = new int[26];
        for(int i = 0; i< len2; i++)
        {
            count[p.charAt(i) - 'a']++;
            windows[s.charAt(i) - 'a']++;
        }
        if(isAnagrams(count,windows)) 
        {
            result.add(0);
        }
        for(int i = 1; i< len1-len2+1; i++)
        {
            windows[s.charAt(i+len2-1) - 'a']++;
            windows[s.charAt(i-1) - 'a']--;
            if(isAnagrams(count,windows))
            {
                result.add(i);
            }
        }
        return result;
    }
    
    public boolean isAnagrams(int[] count, int[] windows)
    {
        for(int i = 0; i< 26; i++)
        {
            if(count[i]!=windows[i]) return false;
        }
        return true;
    }
}