字符串的排列

字符串的排列

给你两个字符串 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

关键点1：判断s1的排列是不是s2的子串，只需要判断s2中是否存在一个子串包含且只包含s1中的全部字符。关键点2：双指针也就是滑动窗口的更新规则。开始想的挺复杂的，先加一个进来，不是s1中的字符就一起右移，是的话就加入。如果是s1的字符则继续添加，还有就是何时停止巴拉巴拉的。反正想的太麻烦了。s1的长度是固定的，直接维护一个长为s1的窗口就好了，时间复杂度也是O(n).

code

class Solution {
public:
    bool isEqual(int cnt1[],int cnt2[])
    {
        for(int i = 0;i < 26;i ++)
        {
            if(cnt1[i] != cnt2[i]) return false;
        }
        return true;
    }
    bool checkInclusion(string s1, string s2) {
        
        if(s1.size() > s2.size()) return false;

        int cnt1[26] = {0};
        int cnt2[26] = {0};

        for(int i = 0;i < s1.size();i ++) cnt1[s1[i] - 'a'] ++;

        int i = 0,j = s1.size() - 1;

        for(int k = i;k <= j;k ++) cnt2[s2[k] - 'a'] ++;

        while(1)
        {
            if(isEqual(cnt1,cnt2)) return true;
            cnt2[s2[i] - 'a'] --;
            i++;
            j++;
            if(j >= s2.size()) break;
            cnt2[s2[j] - 'a'] ++;

        }

        return false;

    }
        
};