LeetCode #567：Permutation in String(字符串的排列)

题目描述

本问题是另一道滑动窗口的典型问题。需要特别注意的是滑动窗口边界右移前后都要对字母出现的频次进行判断，因为可能出现右移前（后）频次相等而右移后（前）不等的情况。

class Solution {
public:
    unordered_map<char, int> flagS1, flagS2;

    bool check(char c) {
        if (flagS1.count(c) && flagS1[c] == flagS2[c]) //c在s1中出现过且在s1和s2中出现的频次相等
            return true;
        return false;
    }

    bool checkInclusion(string s1, string s2) {
        for(int i = 0; i < s1.length(); ++i) {
            flagS1[s1[i]]++;
        }

        int count = 0; //统计s1和s2字母出现频次相等的个数
        for (int l = 0, r = 0; r < s2.size(); ++r) {

            //窗口右边界右移
            if (check(s2[r])) count--; //若右移前频次相等，右移后不等，频次相等的个数减一
            flagS2[s2[r]]++ ;
            if (check(s2[r])) count++; //若右移前频次不等，右移后相等，频次相等的个数加一

            //当窗口大小等于s1长度时，窗口左边界右移
            if (r - l >= s1.size()) { 
                if (check(s2[l])) count--;
                flagS2[s2[l]]--;
                if (check(s2[l])) count++;
                l++;
            }
            if (count == flagS1.size()) return true;
        }

        return false;
    }
};