[leetcode] 76. Minimum Window Substring

ゝ一纸荒年。 2022-06-16 06:16 217阅读 0赞

# 76. Minimum Window Substring #

## 题目： ##

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).

For example,  
S = “ADOBECODEBANC”  
T = “ABC”  
Minimum window is “BANC”.

Note:  
If there is no such window in S that covers all characters in T, return the empty string “”.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

给定两个字符串S和T，找到包含T中所有字符的最小窗口，要求时间复杂度为O（n）。

例如：  
S = “ADOBECODEBANC”  
T = “ABC”  
最小窗口是”BANC”.

## 解题思路 ##

刚开始我的想法是，使用两个map分别记录S和T中的字符和出现的次数。初始统计S和T，如果S中对应字符次数小于T中对于字符次数，则表明S中不包含T中所有字符，直接返回“”。否则就用两个指针分别指向S的头和尾，尝试先尽量将左指针右缩，右指针左缩。最后得到的窗口就是最小窗口。

但是这种方法并不正确，因为假设S中有两个符合要求的窗口，但是最小的窗口在S在左半部分，这样就会在将左指针右缩的时候跳过这个最小窗口。

所以其实应该是扫描整个S，在找到一个符合条件的窗口之后，跟当前最小的窗口比较，从而更新最小窗口。

因此，解答的思路还是使用两指针指向符合窗口的头和尾，然后用一个begin指向最小窗口的头，并且记录一个最小窗口长度。首先尾指针先从S的头往后，找到一个符合条件的窗口，更新最小窗口的头指针和长度，然后头指针也开始右移到下一个查找位置（跳过一个T中的字符m），然后tail继续右移找到下一个字符m，这时又找到了一个符合条件的窗口。重复上述步骤，直到尾指针到达S的最后一个字符。

string minWindow(string s, string t) {
        vector<int> mapt(256);
        for (auto c : t) mapt[c]++;
    
        int head = 0, tail = 0; // two pointers
        int counter = 0; // how many characters contained in s
        int min_winsize = INT_MAX; // minimual window size
        int begin = 0; // point to the begin of minimal window
    
        // first, find substring contains t by increasing tail
        // then, try to minimize window size by increasing head
        while (tail < s.size())
        {
            // if s contains s[tail] in t, increase counter
            if (mapt[s[tail++]]-- > 0) {
                counter ++;
            } 
    
            // find a window 
            while (counter == t.size()) { 
                //update minimal window
                if (tail - head < min_winsize) {
                    begin = head;
                    min_winsize = tail - head;
                }
                //  skip a character in T, this character makes mapt[c] == 0, because the increase in mapt[s[tail++]]--
                if (mapt[s[head++]]++ == 0) 
                    counter --;
            }
        }
        return min_winsize == INT_MAX ? "" : s.substr(begin, min_winsize);
    }