首页 > 代码库 > LeetCode: Minimum Window Substring
LeetCode: Minimum Window Substring
LeetCode: 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).
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 emtpy string ""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
地址:https://oj.leetcode.com/problems/minimum-window-substring/
算法:由于申请两个大小为256的数组,用于统计每一个字符串中各字母的个数,然后用isWindow函数来判断是否由hashS表示的字符串包含由hashT表示的字符串。首先,从S开始找到第一在T中出现的字母位置,记为i,初始化start为i,其中count表示在字符串S[start~i]之间出现在字符串T的字符个数。在每次进入循环时都判断S[start~i]是否可以包含T,如果包含,则根据情况更新最小窗口,并且更新start为下一个出现在字符串T中位置(因为最小的窗口的其实位置一定会出现在字符串T中),注意还要将改变hashS让其表示当前的S[start~i](注意i还是不变);如果不包含,则改变i为下一个出现在字符串T中的位置,并且同时更新对应的hashS。代码:
1 class Solution { 2 public: 3 string minWindow(string S, string T) { 4 int slen = S.size(); 5 int tlen = T.size(); 6 if(slen <= 0 || tlen <= 0) return string(); 7 vector<int> hashT(256,0); 8 vector<int> hashS(256,0); 9 for(int i = 0; i < tlen; ++i)10 ++hashT[T[i]];11 int minNum = slen + 1;12 int minStart = 0, minEnd = 0;13 int i = 0;14 while(i < slen && !hashT[S[i]]){15 ++i;16 }17 if(i >= slen) return string();18 int start = i;19 int count = 1;20 ++hashS[S[i]];21 while(i < slen){22 if(isWindow(hashT,hashS,count,tlen)){23 if(minNum > i-start+1){24 minNum = i-start+1;25 minStart = start;26 minEnd = i;27 }28 --count;29 --hashS[S[start]];30 ++start;31 while(start<slen && !hashT[S[start]]) ++start;32 33 }else{34 ++i;35 while(i<slen && !hashT[S[i]]) ++i;36 if(i < slen){37 ++count;38 ++hashS[S[i]];39 }40 }41 }42 if(minNum == slen + 1){43 return string();44 }45 return S.substr(minStart,minNum);46 }47 bool isWindow(vector<int> &hashT, vector<int> &hashS, int count ,int tlen){48 if(count < tlen)49 return false;50 for(int i = 0; i < 256; ++i){51 if(hashS[i] < hashT[i]){52 return false;53 }54 }55 return true;56 }57 };
LeetCode: Minimum Window Substring