Minimum Window Substring

原題鏈接Minimum Window Substring

要求在源字符串s中找到長度最短的子串，這個子串包含目標字符串t中的所有字符，字符順序沒有要求。

注意在找到的子串中可以包含t中沒有的字符。

乍一看是滑動窗的問題，如果題目要求是”在s中找到子串t，t中字符順序無要求”，那么只需要維護一個長度為t的大小的滑動窗遍歷s即可，這種做法要求找到的子串長度就是t的長度，且無其他t中沒有的字符。

但是難點在本題可以存在t中沒有的字符，比如示例中找到的子串是”BANC”，其中”BAC”是t，而’N’不屬于t。所以，滑動窗的大小是需要動態變化的。

---

根據滑動窗的概念，解決問題時需要兩個指針begin和end分別指向窗口的左邊界和右邊界，在向右移動的過程中右邊加，左邊減，直到滿足條件即可。

但是，由于本題的滑動窗大小不固定，所以在向右移動的過程中，只能右邊加，而不能左邊減。只有當窗口此時覆蓋的區域包含t時，才執行左邊減。

不過，對于右邊加左邊減，仍然不是簡單的將左邊的字符刪掉，將右邊的字符添加進來。

考慮本題，題目中要求找到最短的窗口，這個窗口擁有t中所有的字符。同時根據end的增長，可以確定當窗口覆蓋的區域包含t中所有字符以進行左邊減時，end指向的字符一定在t中。

但是，沒有辦法確定begin指向的字符是否在t中，換句話說，程序一開始只是end在移動，當確定窗口中包含t中所有字符后開始執行左邊減。但是begin的那個位置就沒有動過，不一定就是t中的字符。

所以，在將左邊界指向的字符刪除后，如果當前的窗口仍然包含t中所有字符，那么可以繼續將左邊界刪掉，直到窗口中缺少t中的某個字符時，在進行向右移動。

---

算法的難點就在于，如果確定當前窗口包含t中所有字符，由如何確定當前窗口缺少了t中的某個字符，這個字符是什么。

首先，定義一個容器，這個容器記錄著當前滑動窗缺少t中哪幾個字符，每個字符缺少多少個。這個容器可以是map，也可以是vector，這里定義成

vector<int> map(128, 0);

對于這個容器，規定

• 對于字符ch，map[ch]表示的是當前滑動窗缺少幾個ch
• 如果map[ch]大于0，說明缺少map[ch]個ch
• 如果map[ch]小于0，說明滑動窗中富余|map[ch]|個ch(map[ch]的絕對值個)
• 如果map[ch]等于0，說明滑動窗中不缺少字符ch，也不富余字符ch

對于這個容器的操作，規定

• 通過end遍歷到的字符ch，因為是將end遍歷到的字符添加到滑動窗中，所以執行map[ch]–，即代表加進來一個ch，那么對于ch的缺少數量就應該減一
• 通過begin遍歷到的字符ch，因為是將begin遍歷到的字符從滑動窗中刪除，所以執行map[ch]++，即代表刪掉一個ch，那么對于ch的缺少數量就應該加一

根據這個定義，初始化時將目標字符串t中所以字符放到這個容器中，代表缺少t中所有的字符，即

for(auto ch : t)++map[ch];

不過，注意上述對于容器map的操作規定沒有涉及字符ch是否是目標字符串t中的字符，也就是說在規則中的ch不一定屬于t。這不要緊，因為根據定義，遍歷到的字符ch會執行map[ch]–，那么如果ch不在t中，說明執行后map[ch]小于0，根據小于0的定義，是說明滑動窗中富余|map[ch]|個ch。富余沒關系，關鍵是不能缺少。

那么什么時候代表滑動窗中包含了t中所有元素呢，需要定義一個計數器，這個計數器記錄著當前滑動窗口缺少t中多少個字符。可以用一個int類型的變量，初始時是t的總大小。

那么什么時候更新這個計數器呢，需要根據begin和end遍歷到的字符進行適當更新

適當更新的含義是，有時候更新，有時候不更新0.0

其實是這樣:)

• 如果通過end添加進滑動窗的字符是容器缺少的那個（由上面定義可知缺少的字符一定都是t中的字符），那么計數器減一。怎么判斷是不是容器缺少的呢，可以判斷map[s[end]]是否大于0
• 如果通過begin刪掉的字符剛好是容器中既不缺少的字符，也不是富余的字符（由上面定義可知這些字符也一定都是t中的字符），那么計數器加一。同理判斷依據是map[s[end]]是否等于0

另外需要注意，在進行左邊減的過程中（即已經確定滑動窗中包含t中所有字符），需要不斷記錄最短的滑動窗的位置

代碼如下

class Solution { public:string minWindow(string s, string t) {vector<int> map(128, 0);for(auto ch : t)++map[ch];int counter = t.size();int begin = 0, end = 0;int head = 0;int len = INT_MAX;while(end < s.size()){/* 右邊加，當這個字符是滑動窗缺少的字符時，計數器減一 */if(map[s[end++]]-- > 0) --counter;while(counter == 0){if(end - begin < len){len = end - begin;head = begin;}/* 左邊減，當這個字符是滑動窗不缺也不富余的字符時，計數器加一 */if(map[s[begin++]]++ == 0) ++counter;}}return len == INT_MAX ? "" : s.substr(head, len);} };

本題主要的難點在需要動態改變滑動窗的大小，帶來的問題是右邊加左邊減需要分開執行

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----在字符串s中找到最短的包含字符串t中所有字符的子串，子串中字符顺序无要求且可以有其他字符的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。