lc567.字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

例 1：

输入：s1 = "ab" s2 = "eidbaooo"

输出：true

解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"

输出：false

提示：

1 <= s1.length, s2.length <= 104

s1 和 s2 仅包含小写字母

思路：全排列肯定不可取，长度是10**4；本题采用滑动窗口

不妨令s1的长度<=s2的长度（如果大于s1就肯定不是s2的子串了）

令s1的长度为n,s2的长度为m

如果s1是s2的一种排列子串，意味着可以在s2字符串中找到一段长度为n的符合条件的字符串

两个约束条件：1：长度为n

2：符合条件：即s1可以经过排列形成s2那段字符串

约束1好办，先看约束2，如果用全排列枚举的思路，是不可取的；

那么可以这样想，题目说，s1,s2仅包含小写字母，那么

创建两个统计数组（统计每个字符出现的次数) c1,c2

如果c1=c2 ，那么意味着s1,s2的组成元素相同，即可以通过排列相互转化，即符合题意；

预处理：统计从左往右s1,s2前n个字符分别出现的次数，存入到c1,c2;

如果c1=c2，直接返回return ，否则，滑动窗口进场；

字符串s2第一段长度为n的字符串，是下标从[0,n-1],那么第二段就是[1,n]..

如何得到新的一段滑动窗口的组成部分呢？

删除上一个滑动窗口的第一个元素，加入上一个滑动窗口的最后一个元素的后一个元素

每次得到一段滑动窗口对应的记录数组

只要c2=c1直接返回

如果滑动到底部了还没有return true

直接return false

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int l1 = s1.size(),l2 = s2.size();
        if (l1>l2) return false;
        vector <int> c1(26),c2(26);
        for (int i = 0;i<l1;i++)
        {
            c1[s1[i]-'a']++;
            c2[s2[i]-'a']++;
        }
        if (c1 == c2) return true;//前半部分
        for (int i =1;i+l1<=l2;i++)//后半部分
        {
            c2[s2[i-1]-'a']--;
            c2[s2[i+l1-1]-'a']++;
            if (c1 == c2) return true;
        }
        return false;
    }
};