字符串的排列

描述

给你两个字符串 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 仅包含小写字母

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

题解

这种题目，是明显的滑动窗口算法，相当给你一个 S 和一个 T，请问你 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符？

对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变几个地方：

1、本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，因为排列嘛，显然长度应该是一样的。

2、当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。

至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。

C++代码

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        // need: s1中字符出险次数记录
        // window: 窗口中相应字符的出现次数
        unordered_map<char, int> need, window;
        for(char c: s1) need[c]++;
        int left = 0, right = 0;
        int cnt = 0;
        while(right < s2.size()){
            char c = s2[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(need[c] == window[c]){
                    cnt++;
                }
            }
            while(right - left >= s1.size()){
                if(cnt == need.size())
                    return true;
                char d = s2[left];
                left++;
                if(need.count(d)){
                    if(need[d] == window[d]){
                        cnt--;
                    }
                    window[d]--;
                }
            }
        }
        return false;
    }
};