26
08/2015
[LeetCode] Minimum Window Substring
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.
解题思路：
双指针的办法，两个指针一前一后，若在两个指针之间的区域包含所有的字符，则慢慢缩小后面的指针直到不能再缩小位置，记录当前的最小区域。
有几个技巧需要注意一下：
（1）字符hash可以用数组来表示，可以申请一个长度为256的字符数组。
（2）判断是否找到所有的字符，可以通过计数来表示。
class Solution {
public:
string minWindow(string s, string t) {
int len1 = s.length();
int len2 = t.length();
if(len1 < len2 || len1 ==0 || len2 == 0){
return "";
}
int needFind[256] = {0}; //需要出现的每个字符的次数
for(int i = 0; i<len2; i++){
++needFind[t[i]];
}
int hasFind[256] = {0}; //当前窗口中的每个字符的出现字数
int minStart = 0; //最小起始位置
int minEnd = INT_MAX; //最小终止位置
int findNum = 0; //当前窗口中已经找到的字符个数
for(int start = 0, end = 0; end < len1; ++end){
if (needFind[s[end]] == 0){ //不再t中的字符直接忽略
continue;
}
++hasFind[s[end]];
if(hasFind[s[end]]<=needFind[s[end]]){
++findNum;
}
if(findNum == len2){
while(findNum == len2){ //这里不断缩小范围
if(needFind[s[start]] == 0){
++start;
}else if(hasFind[s[start]] > needFind[s[start]]){
--hasFind[s[start]];
++start;
}else if(hasFind[s[start]] == needFind[s[start]]){
--hasFind[s[start]];
--findNum;
++start;
}
}
if(minEnd - minStart > end - start + 1){
minEnd = end;
minStart = start - 1;
}
}
}
if(minEnd == INT_MAX){
return "";
}
return s.substr(minStart, minEnd - minStart + 1);
}
};
0 条评论