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元起,快前往官网查看详情吧


分享文章:LeetCode刷题系列--567.字符串的排列-创新互联
分享URL:http://myzitong.com/article/jedgh.html