给出两个字符串 s和 t,要求在 s中找出最短的包含 t中所有字符的连续子串。
数据范围:0 > |S|,|T| \le100000>∣S∣,∣T∣≤10000,保证s和t字符串中仅包含大小写英文字母
要求:进阶:空间复杂度O(n)O(n), 时间复杂度O(n)O(n)
例如:
S ="XDOYEZODEYXNZ"S="XDOYEZODEYXNZ"
T ="XYZ"T="XYZ"
找出的最短子串为"YXNZ""YXNZ".
注意:
如果 s中没有包含 t中所有字符的子串,返回空字符串 “”;
满足条件的子串可能有很多,但是题目保证满足条件的最短的子串唯一。
示例1
输入:
"XDOYEZODEYXNZ","XYZ"
复制返回值:
"YXNZ"
复制
示例2
输入:
"abcAbA","AA"
复制返回值:
"AbA"
这个题刷了很久没搞定,看了大牛的操作才明白。大概思路跟我一致,细节处理人家很到位。
class Solution {public:/*** * @param S string字符串 * @param T string字符串 * @return string字符串*/string minWindow(string S, string T) {int minLen = INT32_MAX;int left = 0,right = 0,count = 0,start = 0;unordered_map<char, int> target,window;for(char c : T){target[c]++;}while(right < S.size()){char c = S[right];right++;if(target.count(c)){window[c]++;if(window[c] == target[c]){count++;}}while(count == target.size()){char c = S[left];if (right-left < minLen) {start = left;minLen = right-left;}if(target.count(c)){if(target[c] == window[c]){break;}window[c]--;}left++;}}return minLen == INT32_MAX ? "" : S.substr(start,minLen);}};
如果觉得《滑动窗口大杀器 牛逼》对你有帮助,请点赞、收藏,并留下你的观点哦!