1 class Solution { 2 public: 3 bool checkInclusion(string s1, string s2) { 4 vector<int> m1(26); 5 vector<int> m2(26); 6 int len1=s1.length(); 7 int len2=s2.length(); 8 if(len2<len1) 9 return false; 10 for(int i=0;i<len1;i++){ 11 m1[s1[i]-'a']++; 12 m2[s2[i]-'a']++; 13 } 14 int count=0; 15 for(int i=0;i<26;i++){ 16 if(m2[i]==m1[i]) 17 count++; 18 } 19 if(count==26) 20 return true; 21 int left=0,right=len1-1; 22 while(right<len2-1){ 23 int pos = s2[left]-'a'; 24 if(m1[pos]==m2[pos]) 25 count--; 26 m2[pos]--; 27 if(m1[pos]==m2[pos]) 28 count++; 29 left++; 30 31 right++; 32 pos = s2[right]-'a'; 33 if(m1[pos]==m2[pos]) 34 count--; 35 m2[pos]++; 36 if(m1[pos]==m2[pos]) 37 count++; 38 if(count==26) 39 return true; 40 } 41 return false; 42 } 43 };
用两个数组辅助,一个数组存放待匹配子序列的字符统计,另一个数组存放当前滑动窗口的字符统计
用一个变量count来存放两个数组的元素匹配计数
每次更新滑动窗口时,left+1,right+1,同时更新滑动窗口对应数组和count
这里需要注意的是,在更新count时,要考虑原来匹配,更新后不匹配,和原来不匹配,更新后匹配的情况。