【leetcode】567. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).

示例2:

输入: s1= “ab” s2 = “eidboaoo”
输出: False

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这是一个滑动窗口的问题，　只要保证入窗口和出窗口的操作是互逆的就可以。

窗口大小为窗口内有几个字符属于字符串ｔ，只要滑入一个新的属于ｔ的就将窗口变长一些，
滑出去一个就将窗口变小。

然后维护窗口大小。

当窗口变成t的长度的时候，就意味着找到了。

代码

class Solution {
   
public:
    bool checkInclusion(string t, string s) {
   
        int count[128] = {
    0 };
        for (char c : t) count[c]++;
        for (int l = 0, r = 0, len = 0; r < s.size(); r++) {
   
            if (--count[s[r]] >= 0) ++len;
            while (r - l + 1 > len && ++ count[s[l++]] > 0) --len; 
            if (len == t.size()) return true;
        }
        return false;
    }
};

总结

滑动窗口，一端滑入，一端滑出。
滑入和滑出操作互为逆操作就可以保证问题的原貌，
明确滑动窗口的意义，然后来维护一个滑动窗口。