【LeetCode-中等】567. 字符串的排列 - 滑动窗口_unordered_set occ; int len = s.length(); if(

567. 字符串的排列

解法：滑动窗口
由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列。
记 s1 的长度为 n，遍历 s2 中的每个长度为 n 的子串，判断子串和 s1 中每个字符的个数是否相等，若相等则说明该子串是 s1 的一个排列。
滑动窗口每向右滑动一次，就多统计一次进入窗口的字符，少统计一次离开窗口的字符。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_set<char> occ;
        int len1=s1.size(),len2=s2.size();
        if(len1>len2) return false;
        vector<int> a1(26), a2(26);
        for(int i=0;i<len1;i++){
            a1[s1[i]-'a']++;
            a2[s2[i]-'a']++;
        }
        if(a1==a2) return true;
        for(int i=len1;i<len2;i++){
            a2[s2[i]-'a']++;
            a2[s2[i-len1]-'a']--;
            if(a1==a2) return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

注意 s1 长度比 s2 长的的情况，即if(len1>len2) return false;