一、题目说明
题目76. Minimum Window Substring,求字符串S中最小连续字符串,包括字符串T中的所有字符,复杂度要求是O(n)。难度是Hard!
二、我的解答
先说我的思路:
(1)统计t中每个字符出现的次数,
(2)用hash存储s中出现t中字符的位置,
(3)计算最短字符串。
思路有了,惭愧的是,这个题目,我没做出来。
后来参考大神的实现了,用“滑动窗口”实现。
代码如下:
class Solution{
public:
string minWindow(string s,string t){
if(s.empty() || t.empty()) return "";
int left=0,right=0;
string res = s;
int minLen = INT_MAX;
int start = 0;
unordered_map<char,int> window;//当前「窗口」中包含的字符及出现的次数
unordered_map<char,int> needs;//t 中包含的字符及出现次数
//统计字符串t中各个字符的数量
for(char ch:t){
needs[ch]++;//如果该 key不存在,C++ 会自动创建这个 key,并把 map[key] 赋值为 0
}
int match = 0;//记录 window 中已经有多少字符符合要求了
while(right<s.size()){
char c1 = s[right];
if(needs.count(c1)){
window[c1]++;
if(window[c1]==needs[c1]){
match++;//字符 c1 的出现次数符合要求了
};
}
right++;
//window 中的字符串已符合 needs 的要求了
while(match==needs.size()){
//缩减res
if(right-left<minLen){
start = left;
minLen = right - left;
}
char c2 = s[left];
if(needs.count(c2)){
window[c2]--;
if(window[c2]<needs[c2]){
match--;
}
}
left++;
}
}
return minLen == INT_MAX ? "" : s.substr(start, minLen);
}
};
性能一般:
Runtime: 28 ms, faster than 45.63% of C++ online submissions for Minimum Window Substring.
Memory Usage: 10.2 MB, less than 68.00% of C++ online submissions for Minimum Window Substring.
三、优化措施
我消化消化再说。