76. Minimum Window Substring

2021-04-04 20:25

阅读：503

标签：character minimum tee ++ ring bst 去掉 tput 字符

问题描述：

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

解题思路：

这道题我们可以用滑动窗口来解决。

首先我们先将t中的字符放到hashmap中，对应的是字符和它出现的次数。

然后我们遍历s，并用滑动窗口来寻找最短的子串。

首先向窗口里加入字符，即移动right。

在移动right的途中，遇见存在于t中的字符，对map中t的出现次数-1，并且当map[s[right]] > 0 时对总计数count+1。

当count与t.size()相等时，说明当前窗口[left, right]中包括了t中所有的字符，我们可以尝试移动left来去掉当前窗口中不属于t中的字符串，并且更新返回字符串ret。

若当前字符是t中的字符串，我们需要对m中该字符串出现的次数+1，若此时m[s[left]] > 0 说明移走了t中的字符串，当前窗口不包含t中所有字符，count需要-1。

再继续移动right

代码：

class Solution {
public:
    string minWindow(string s, string t) {
        if(t.size() > s.size())
            return "";
        unordered_mapchar, int> m;
        for(char c : t){
            m[c]++;
        }
        int left = 0;
        int minLen = s.size()+1;
        int count = 0;
        string ret;
        for(int i = 0; i ){
            if(m.count(s[i])){
                m[s[i]]--;
                if(m[s[i]] >= 0)
                    count++;
                while(count == t.size()){
                    if((i - left + 1)  minLen){
                        minLen = i - left + 1;
                        ret = s.substr(left, minLen);
                    }
                    if(m.count(s[left]) != 0){
                        m[s[left]]++;
                        if(m[s[left]] > 0)
                            count--;
                    }
                    left++;
                }
            }
        }
        return ret;
    }
};

76. Minimum Window Substring

标签：character minimum tee ++ ring bst 去掉 tput 字符

原文地址：https://www.cnblogs.com/yaoyudadudu/p/9175919.html

上一篇：树莓派配置Web服务器

下一篇：Python如何入门？搭配这些游戏，学习高效还有趣

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：76. Minimum Window Substring
文章链接：http://soscw.com/index.php/essay/71962.html

亲，登录后才可以留言！

76. Minimum Window Substring

评论

热门文章

推荐文章

最新文章

置顶文章