LeetCode刷题系列--567.字符串的排列-创新互联

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

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

示例 1：

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

示例 2：

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

思路：我写了首诗，把滑动窗口算法变成了默写题 :: labuladong的算法小抄

利用滑动窗口法

c++

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        mapneed,window;

        for(char c:s1) {
            need[c]++;
        }

        int left=0,right=0,valid=0;

        //  这个 while 循环是窗口法的标准框架
        while(right< s2.size()){
            char c = s2[right];
            // 扩大窗口
            right++;
            if(need.count(c)>0) {
                window[c]++;
                if(window[c] == need[c]) {
                    valid++;
                }
            }

            // 若是窗口长度大于 s1 的长度，则缩小窗口
            while(right-left>=s1.size()) {

                // 说明 s1 中的字符均在  s2[left,right-1] 子串中出现过，且字符数量也一致
                if( valid == need.size()) {
                    return true;
                }

                char cc = s2[left];
                // 缩小窗口
                left++;
                
                if(need.count(cc)>0) {
                    if(window[cc]==need[cc]) {
                        valid--;
                    }
                    window[cc]--;
                }

            }

        }

        return false;

    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧