题目

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.

大意

找出包含第二个字符的最短子串

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() == 0 || t.length() > s.length()) {
            return "";
        }
        vector<int> freq(256, 0);
        for (char c : t) {
            freq[c]++;
        }
        int l = 0, h = 0, counter = 0, minLen = INT_MAX;
        string res = "";
        while (h < s.length()) {
            if (freq[s[h++]]-- > 0) {
                counter++;
            }
            while (counter == t.length()) {
                // [l, h)
                if (h - l < minLen) {
                    res = s.substr(l, h - l);
                    minLen = res.length();
                }
                if (++freq[s[l++]] > 0) {
                    counter--;
                } 
            }
        }
        return res;
    }

思路

求子串的问题一般都是哈希表和two piont 相结合.

先把t字符串读到哈希表中.

本题主要分两个阶段,刚开始初始左右指针都在s的起点处, 先不断的移动右指针,直到包含了所有的T字符,(用counter代表一共S中有了多少T里的字符,当counter等于T.size的时候,代表此时,左指针和右指针围住的子串符合题意了,这时进入第二个阶段,不断的移动左指针,去除掉一些左边不必要的指针,freq是每个字符在T中需要的个数,所以在第二个阶段,就是如果freq[s[l++]]++后,大于0,说明左指针和右指针已经围不住包含T的子串了,此时count–. count–后,会跳出第二个while循环,又会重新去移动右边的指针.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
下面是用哈希表写 ,主要看上面那个解法把
class Solution {
public:
    string minWindow(string s, string t) {
        map<char,int> mp;
        for(int i=0;i<t.size();i++)
        {
            mp[t[i]]++;
        }
        int tot =t.size(); 
        int ret = s.size() + 1;
        int head = 0, ansHead = 0;
        for(int i=0;i<s.size();i++)
        {
            if(mp.find(s[i])->second>0)   tot--;
            mp.find(s[i])->second--; //尾坐标右移,直接就加入了.
            while(tot==0)
            {
                if (ret > i - head + 1) { ret = i - head + 1; ansHead = head;}
                    // move s[head]
                if (mp.find(s[ head ])->second == 0) tot ++;
                mp.find(s[ head ])->second++;
                head ++;
            }
        }
        if (ret > s.size()) return "";
        return s.substr(ansHead, ret);
    }
};