567. Permutation in String

------------恢复内容开始------------

仅供自己学习

 

思路:

还是滑动窗口,但是这里,因为他的排列不一定和s1的一样,所以要考虑怎么判断s2有s1的排列。这里考虑转化成对每个字母的计数来进行判断,这样就可不关心s2是如何排列的了,当我们将s1的每个字母计数后,再将s2中 s1.length长度的子串计数,判断是否一样,不一样则窗口向右移,并且再次判断即可。

这个技巧很有用,就是利用 s[ i ]- 'a',对字母映射到整数进行存储,同时也方便计数。

 

代码:

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

 

上述的方法比较直白,还可以用更节约空间的方法,就是使用一个vector,然后用一个diff变量来存储不同的字符数,我们首先把s1的所有字符映射到整数上,然后进行计数-1,在对s2的进行+1,然后我们遍历这个计数后的vector,是否有不为0的元素,有的话diff+1,说明s1与当前的s2存在差异性字符。然后我们从s2的第n+1个元素开始,将第n+1个元素放进x这个变量,然后将 第1个元素放进y的变量。也即 第n+i放进x变量,第i-n个元素放进y变量。因为对于x变量的元素,如果s[x]为0,那么新加入一个元素就存在差异,diff+1,并且s[X]++,这S[X]++之后如果S[X]为0,那么就把diff--,因为这个差异不存在了,对于S[y],如果等于0,那么差异就加一,并且s[y]--,如果这之后s[y]--后为0,也是差异就不存在了。当diff为0,那么此时s2的子串和s1就没差异那么就可以返回true,当循环结束都还存在差异那么就返回false

 

代码:

 1 class Solution {
 2 public:
 3     bool checkInclusion(string s1, string s2) {
 4         int n=s1.length(),m=s2.length();
 5         if(n>m) return false;
 6         vector<int> s(26);
 7         for(int i=0;i<n;++i){
 8             --s[s1[i]-'a'];
 9             ++s[s2[i]-'a'];
10         }
11         int diff=0;
12         for(auto a:s){
13             if(a!=0) diff++;
14         }
15         if(diff==0) return true;
16         for(int i=n;i<m;++i){
17             int x=s2[i]-'a',y=s2[i-n]-'a';
18             if(x==y) continue;
19             if(s[x]==0)
20                 ++diff;
21             ++s[x];
22             if(s[x]==0)
23                 --diff;
24             
25             if(s[y]==0)
26                 ++diff;
27             --s[y];
28             if(s[y]==0)
29                 --diff;
30             if(diff==0) return true;
31         }
32         
33         return false;
34     }
35 };

 

上一篇:LeetCode 31. 下一个排列(线性扫描)


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