剑指 Offer II 014. 字符串中的变位词 滑动窗口

剑指 Offer II 014. 字符串中的变位词
滑动窗口

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        m,n=len(s1),len(s2)
        if m>n:
            return False
        cnt_s1=Counter(s1)
        for i in range(n-m+1):              # i为0-n-m
            if Counter(s2[i:i+m])==cnt_s1:     #不包括索引i+m
                return True
        return False
1
2
3
4
5
6
7
8
9
10

双指针，过程中保证dict[left]至dict[right]中每个值都小于0，说明没有多余字母或其他字母，且[left,right]的长度刚好为m，说明每个字母个数都相同，不然在++dict[x]后必定存在dict[x]>0

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
		int m=s1.length(),n=s2.length();
		vector<int>dict(26);
		for(int i=0;i<m;++i){
			--dict[s1[i]-'a'];
		}
		int left=0;
		for(int right=0;right<n;++right){
			int x=s2[right]-'a';
			++dict[x];
			while (dict[x]>0){
				--dict[s2[left]-'a'];
				++left;
			}
			if(right-left+1==m) return true;
		}
		return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21