題目

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中所有字符時，收縮頭指針，直到不能收縮為止。記錄此時的窗口長度和起始位置。然后重復(fù)剛才的操作，找到最小的窗口。
有一個比較難的地方是如何判斷出現(xiàn)了T中所有的字符。這個可以使用一個expected數(shù)組來記錄每個字符應(yīng)該出現(xiàn)的次數(shù)，一個appeared數(shù)組來記錄每個字符在頭尾指針之間出現(xiàn)的次數(shù)，以及一個變量n_apd記錄在頭尾指針之間出現(xiàn)的有效字符的數(shù)目。當(dāng)n_apd==T.size()時，可以認(rèn)為滿足了條件。

實(shí)現(xiàn)

class Solution {
public:
    string minWindow(string s, string t) {
        const int ASCII_MAX=256;
        int appeared[ASCII_MAX];
        int expected[ASCII_MAX];
        fill(appeared, appeared+ASCII_MAX, 0);
        fill(expected, expected+ASCII_MAX, 0);
        int wnd_min=INT_MAX, ans_start=0, ans_end=0;
        for(int i=0; i<t.size(); i++)
            expected[t[i]]++;
        int wnd_end, wnd_start=0, n_apd=0;
        for(wnd_end=0; wnd_end<s.size(); wnd_end++){
            if(expected[s[wnd_end]]>0){
                appeared[s[wnd_end]]++;
                if(appeared[s[wnd_end]]<=expected[s[wnd_end]])
                    n_apd++;
            }
            if(n_apd==t.size()){
                while(appeared[s[wnd_start]]>expected[s[wnd_start]] || expected[s[wnd_start]]==0){
                    if(expected[s[wnd_start]]>0) appeared[s[wnd_start]]--;
                    wnd_start++;
                }
                if(wnd_min>wnd_end-wnd_start+1){
                    wnd_min = wnd_end - wnd_start + 1;
                    ans_start = wnd_start; 
                    ans_end = wnd_start;
                }
            }
        }
        if(wnd_min==INT_MAX) return "";
        else return s.substr(ans_start, wnd_min);
    }
};

思考

這題一開始在數(shù)據(jù)結(jié)構(gòu)的選擇上卡住了。最后使用了最基本的數(shù)組就完成了操作。再一次讓我想起了扎克伯格的一句話
Done is better than perfect.