题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:如果 s 中存在这样的子串,我们保证它是唯一的答案。
样例
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
算法1
(差值哈希) $O(n)$
此题跟LC438题如出一辙,可以使用匹配串和模式串字符种类的差值来做。但与LC438相比难度增大的一点在于,窗的长度不再是固定的,窗只要涵盖模式串的所有字符即可。但此题使用差值来做会导致条件判断等比较麻烦,调试也会比较慢。
C++ 代码
class Solution {
public:
string minWindow(string s, string t) {
#ifdef _commet
输入:s匹配串 t模式串
输出:s 中涵盖 t 所有字符的最小子串
此题跟LC438题如出一辙,需要使用匹配串和模式串字符种类的差值来做。但与LC438相比难度增大的一点在于,窗的长度不再是固定的,窗只要涵盖模式串的所有字符即可。
#endif
unordered_map<char, int> diff;//键:字符种类 值:每种字符种类的出现次数的差
string res="";
for(auto &c : t)
diff[c]++;
int cnt = 0,tar = diff.size();
for(int i = 0, j = 0; i<s.size(); i++)
{
//第i个元素入窗,当该元素种类在模式串里有时,该字符种类差值减1(由于涵盖关系,此处已经修改)。当入窗之后差值等于0,该种类匹配,计数+1
if(diff.count(s[i]))//check 有没有s[i]这个key,有再操作
if(!--diff[s[i]])
cnt++;
//当j已经多余的时候(不存在key或者diff[s[j]]<0,即有多余的该字符),第j个元素可以出窗,当该元素种类在模式串里有时,才将该字符种类差值加1(由于涵盖关系,此处已经修改)。当出窗前差值为0,则出窗后种类将会不匹配,计数-1。由于窗长不再固定,因此需要使用while
while (!diff.count(s[j]) || diff[s[j]] < 0)
{
if(diff.count(s[j]))//check 有没有s[j]这个key,有再操作
if(!diff[s[j]]++)
cnt--;
if(j==s.size()-1) break;//遍历到s字符串末尾无法继续遍历 跳出循环
j++;
}
if(cnt == tar)
if (res.empty() || i - j + 1 < res.size())
res = s.substr(j, i - j + 1);
}
return res;
}
};
算法2
(用匹配串和模式串两个哈希) $O(n)$
用匹配串和模式串两个哈希来做,虽然空间上会大一倍甚至更多(模式串长度小),但是可以有效避免hash.count()判断的问题,写起来会方便些
C++ 代码
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> hs, ht;
for (auto c: t) ht[c] ++ ;
string res;
int cnt = 0;
for (int i = 0, j = 0; i < s.size(); i ++ ) {
hs[s[i]] ++ ;
if (hs[s[i]] <= ht[s[i]]) cnt ++ ;
while (hs[s[j]] > ht[s[j]]) hs[s[j ++ ]] -- ;
if (cnt == t.size()) {
if (res.empty() || i - j + 1 < res.size())
res = s.substr(j, i - j + 1);
}
}
return res;
}
};