题解 | #最小覆盖子串#

最小覆盖子串

http://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac

  1. 典型的滑动窗口问题
class Solution {
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // write code here
        unordered_map<char,int> need, window;
        //首先,初始化 window 和 need 两个哈希表,记录窗口中的字符和需要凑齐的字符:
        for(char c:T){
            need[c]++;
        }
        //然后,使用 left 和 right 变量初始化窗口的两端,不要忘了,区间 [left, right) 是左闭右开的,所以初始情况下窗口没有包含任何元素:
        int left = 0,right = 0;
        int valid = 0;//其中 valid 变量表示窗口中满足 need 条件的字符个数,如果 valid 和 need.size 的大小相同,则说明窗口已满足条件,已经完全覆盖了串 T。

        //开始滑动
        //记录最小覆盖子串的起始索引及长度
        int start = 0, len = INT_MAX;
        while(right<S.size()){
             // c 是将移入窗口的字符
            char c = S[right];
            // 右移窗口
            right++;
             // 进行窗口内数据的一系列更新
            if(need.count(c)){
                window[c]++;
                if(window[c]==need[c]){
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while(valid==need.size()){
                 // 在这里更新最小覆盖子串
                if(right-left<len){
                    start = left;
                    len = right - left;
                }
                //  d 是将移出窗口的字符
                char d = S[left];
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if(need.count(d)){
                    if(window[d] == need[d]){
                        valid--;
                    }

                    window[d]--;
                }


            }


        }


        return len == INT_MAX? "": S.substr(start,len);


    }
};
算法解析 文章被收录于专栏

这里主要是算法岗的自我思路总结

全部评论

相关推荐

头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 10:39
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务