[LeetCode] 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).

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.

這道題給了我們一個(gè)原字符串S，還有一個(gè)目標(biāo)字符串T，讓在S中找到一個(gè)最短的子串，使得其包含了T中的所有的字母，并且限制了時(shí)間復(fù)雜度為 O(n)。這道題的要求是要在 O(n) 的時(shí)間度里實(shí)現(xiàn)找到這個(gè)最小窗口字串，暴力搜索 Brute Force 肯定是不能用的，因?yàn)楸闅v所有的子串的時(shí)間復(fù)雜度是平方級(jí)的。那么來想一下，時(shí)間復(fù)雜度卡的這么嚴(yán)，說明必須在一次遍歷中完成任務(wù)，當(dāng)然遍歷若干次也是 O(n)，但不一定有這個(gè)必要，嘗試就一次遍歷拿下！那么再來想，既然要包含T中所有的字母，那么對(duì)于T中的每個(gè)字母，肯定要快速查找是否在子串中，既然總時(shí)間都卡在了 O(n)，肯定不想在這里還浪費(fèi)時(shí)間，就用空間換時(shí)間（也就算法題中可以這么干了，七老八十的富翁就算用大別野也換不來時(shí)間啊。依依東望，望的就是時(shí)間吶 T.T），使用 HashMap，建立T中每個(gè)字母與其出現(xiàn)次數(shù)之間的映射，那么你可能會(huì)有疑問，為啥不用 HashSet 呢，別急，講到后面你就知道用 HashMap 有多妙，簡直妙不可言～

目前在腦子一片漿糊的情況下，我們還是從簡單的例子來分析吧，題目例子中的S有點(diǎn)長，換個(gè)短的 S = "ADBANC"，T = "ABC"，那么肉眼遍歷一遍S唄，首先第一個(gè)是A，嗯很好，T中有，第二個(gè)是D，T中沒有，不理它，第三個(gè)是B，嗯很好，T中有，第四個(gè)又是A，多了一個(gè)，禮多人不怪嘛，收下啦，第五個(gè)是N，一邊涼快去，第六個(gè)終于是C了，那么貌似好像需要整個(gè)S串，其實(shí)不然，注意之前有多一個(gè)A，就算去掉第一個(gè)A，也沒事，因?yàn)榈谒膫€(gè)A可以代替之，第二個(gè)D也可以去掉，因?yàn)椴辉赥串中，第三個(gè)B就不能再去掉了，不然就沒有B了。所以最終的答案就"BANC"了。通過上面的描述，你有沒有發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象，先擴(kuò)展，再收縮，就好像一個(gè)窗口一樣，先擴(kuò)大右邊界，然后再收縮左邊界，上面的例子中右邊界無法擴(kuò)大了后才開始收縮左邊界，實(shí)際上對(duì)于復(fù)雜的例子，有可能是擴(kuò)大右邊界，然后縮小一下左邊界，然后再擴(kuò)大右邊界等等。這就很像一個(gè)不?；瑒?dòng)的窗口了，這就是大名鼎鼎的滑動(dòng)窗口 Sliding Window 了，簡直是神器啊，能解很多子串，子數(shù)組，子序列等等的問題，是必須要熟練掌握的??！

下面來考慮用代碼來實(shí)現(xiàn)，先來回答一下前面埋下的伏筆，為啥要用 HashMap，而不是 HashSet，現(xiàn)在應(yīng)該很顯而易見了吧，因?yàn)橐y(tǒng)計(jì)T串中字母的個(gè)數(shù)，而不是僅僅看某個(gè)字母是否在T串中出現(xiàn)。統(tǒng)計(jì)好T串中字母的個(gè)數(shù)了之后，開始遍歷S串，對(duì)于S中的每個(gè)遍歷到的字母，都在 HashMap 中的映射值減1，如果減1后的映射值仍大于等于0，說明當(dāng)前遍歷到的字母是T串中的字母，使用一個(gè)計(jì)數(shù)器 cnt，使其自增1。當(dāng) cnt 和T串字母個(gè)數(shù)相等時(shí)，說明此時(shí)的窗口已經(jīng)包含了T串中的所有字母，此時(shí)更新一個(gè) minLen 和結(jié)果 res，這里的 minLen 是一個(gè)全局變量，用來記錄出現(xiàn)過的包含T串所有字母的最短的子串的長度，結(jié)果 res 就是這個(gè)最短的子串。然后開始收縮左邊界，由于遍歷的時(shí)候，對(duì)映射值減了1，所以此時(shí)去除字母的時(shí)候，就要把減去的1加回來，此時(shí)如果加1后的值大于0了，說明此時(shí)少了一個(gè)T中的字母，那么 cnt 值就要減1了，然后移動(dòng)左邊界 left。你可能會(huì)疑問，對(duì)于不在T串中的字母的映射值也這么加呀減呀的，真的大丈夫（帶膠布）嗎？其實(shí)沒啥事，因?yàn)閷?duì)于不在T串中的字母，減1后，變-1，cnt 不會(huì)增加，之后收縮左邊界的時(shí)候，映射值加1后為0，cnt 也不會(huì)減少，所以并沒有什么影響啦，下面是具體的步驟啦：

- 先掃描一遍T，把對(duì)應(yīng)的字符及其出現(xiàn)的次數(shù)存到 HashMap 中。

- 然后開始遍歷S，就把遍歷到的字母對(duì)應(yīng)的 HashMap 中的 value 減一，如果減1后仍大于等于0，cnt 自增1。

- 如果 cnt 等于T串長度時(shí)，開始循環(huán)，紀(jì)錄一個(gè)字串并更新最小字串值。然后將子窗口的左邊界向右移，如果某個(gè)移除掉的字母是T串中不可缺少的字母，那么 cnt 自減1，表示此時(shí)T串并沒有完全匹配。

解法一：

class Solution {
public:
    string minWindow(string s, string t) {
        string res = "";
        unordered_map<char, int> letterCnt;
        int left = 0, cnt = 0, minLen = INT_MAX;
        for (char c : t) ++letterCnt[c];
        for (int i = 0; i < s.size(); ++i) {
            if (--letterCnt[s[i]] >= 0) ++cnt;
            while (cnt == t.size()) {
                if (minLen > i - left + 1) {
                    minLen = i - left + 1;
                    res = s.substr(left, minLen);
                }
                if (++letterCnt[s[left]] > 0) --cnt;
                ++left;
            }
        }
        return res;
    }
};

這道題也可以不用 HashMap，直接用個(gè) int 的數(shù)組來代替，因?yàn)?ASCII 只有256個(gè)字符，所以用個(gè)大小為 256 的 int 數(shù)組即可代替 HashMap，但由于一般輸入字母串的字符只有 128 個(gè)，所以也可以只用 128，其余部分的思路完全相同，雖然只改了一個(gè)數(shù)據(jù)結(jié)構(gòu)，但是運(yùn)行速度提高了一倍，說明數(shù)組還是比 HashMap 快啊。還可以進(jìn)一步的優(yōu)化，沒有必要每次都計(jì)算子串，只要有了起始位置和長度，就能唯一的確定一個(gè)子串。這里使用一個(gè)全局變量 minLeft 來記錄最終結(jié)果子串的起始位置，初始化為 -1，最終配合上 minLen，就可以得到最終結(jié)果了。注意在返回的時(shí)候要檢測一下若 minLeft 仍為初始值 -1，需返回空串，參見代碼如下：

解法二：

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> letterCnt(128, 0);
        int left = 0, cnt = 0, minLeft = -1, minLen = INT_MAX;
        for (char c : t) ++letterCnt[c];
        for (int i = 0; i < s.size(); ++i) {
            if (--letterCnt[s[i]] >= 0) ++cnt;
            while (cnt == t.size()) {
                if (minLen > i - left + 1) {
                    minLen = i - left + 1;
                    minLeft = left;
                }
                if (++letterCnt[s[left]] > 0) --cnt;
                ++left;
            }
        }
        return minLeft == -1 ? "" : s.substr(minLeft, minLen);
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(76.最小窗口子串)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)最小窗口子串內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論