難度困難441

給你一個字符串 S、一個字符串 T，請在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

輸入: S = "ADOBECODEBANC", T = "ABC" 輸出: "BANC"

說明：

• 如果 S 中不存這樣的子串，則返回空字符串?""。
• 如果 S 中存在這樣的子串，我們保證它是唯一的答案。

思路：

1.首先遍歷一遍t，用map記錄每個字母出現(xiàn)的次數(shù)。
2.從頭開始遍歷s，當(dāng)t中的所有字母在s中都遍歷到的時候，將結(jié)果暫存入ans中，然后逐漸從左端縮短子串，看是否子串仍滿足條件。一次次的刷新最小子串的長度，將這一過程中得到的最小子串存入ans中。當(dāng)不滿足條件時，繼續(xù)向右擴(kuò)展，知道再次滿足條件，然后重復(fù)上面的過程，直到將s遍歷完。

?

class Solution { public:string minWindow(string s, string t) {string result = "";int ns = s.length();int nt = t.length();map<char,int> map_t;for(int i=0;i<nt;++i){map_t[t[i]]++;}int count = 0; int minlen = INT_MAX;for(int i=0,left = 0;i<ns;++i){if(--map_t[s[i]]>=0)count++;while(count==nt){if(i-left+1<minlen){minlen = i-left+1;result = s.substr(left,minlen);}if(++map_t[s[left++]]>0)count--;}}return result;} };

?

總結(jié)

以上是生活随笔為你收集整理的最小覆盖字串—leetcode76的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。