[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 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);
}
};
转载请注明： » [LeetCode] Minimum Window Substring
<!--
-->
原文作者：；如有侵权，请联系管理员删除。
请登录后发表评论
登录
全部评论
