567. Permutation in String

 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时,要考虑原来匹配,更新后不匹配,和原来不匹配,更新后匹配的情况。

上一篇:python-输入的组合或排列,给定长度


下一篇:Photoshoot