C++描述 LeetCode 567. 字符串的排列

  大家好，我叫亓官劼（qí guān jié ），在CSDN中记录学习的点滴历程，时光荏苒，未来可期，加油~博主目前仅在CSDN中写博客，唯一博客更新的地址为：亓官劼的博客 ，同时正在尝试在B站中做一些内容分享，B站主页为： 亓官劼的B站主页

本文原创为亓官劼，请大家支持原创，部分平台一直在恶意盗取博主的文章！！！
若需联系博主，可以联系本人微信：qiguanjie2015

---

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

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

示例1:

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

示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False

注意：

1. 输入的字符串只包含小写字母
2. 两个字符串的长度都在 [1, 10,000] 之间

解题思路

滑动窗口。使用两个数组分别存储s1的所有字母的个数和s2中在当前长度与s1相同的窗口中所有字母出现的次数。如果两个数组相同，即在一个窗口内，s2长度与s1长度相同的子串中拥有的各个字母的数量与s1相同，则s2包含s1的排列.

算法实现

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> vec1(26),vec2(26);
        int len1 = s1.length(),len2 = s2.length();
        if(len1 > len2)
            return false;
        // 初始化vec1,vec2
        for(int i = 0 ; i < len1; i++)
            vec1[s1[i]-'a']++,vec2[s2[i]-'a']++;
        if(vec1 == vec2)
            return true;
        for(int i = len1; i < len2; i++){
            vec2[s2[i]-'a']++;
            vec2[s2[i-len1]-'a']--;
            // 如果当前窗口内，两者含有字母相同，则s2包含s1的排列
            if(vec1 == vec2)
                return true;
        }
        return false;
    }
};