“给定两个字符串st,返回字符串s中覆盖t所有字符的最小子串。”
题目链接:
来源:力扣(LeetCode)
链接:76. 最小覆盖子串 - 力扣(LeetCode) (leetcode-cn.com)
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
注意:
示例 1:
输入: s = "ADOBECODEBANC", t = "ABC"
输出: "BANC"
示例 2:
输入: s = "a", t = "a"
输出: "a"
哈哈 经典滑动窗口的题目。
题意要求返回字符串s中覆盖t全部字符的最小子串,可以将包含t的子串的看做可行窗口。
在滑动窗口中会有两个指针,一个用于延伸现有窗口的指针,一个用于收缩窗口的指针。
那如果判断当前串口包含所有t所需的字符呢?可以用一个哈希表来表示t中所有的字符及数量。
如果这个哈希表中的对应的个数都不小于t的哈希表中各个字符的个数,那么当前窗口是可行的。
代码参考:
public class Solution
{
Dictionary<char, int> sDic = new Dictionary<char, int>();
Dictionary<char, int> tDic = new Dictionary<char, int>();
public string MinWindow(string s, string t)
{
sDic.Clear();
tDic.Clear();
//考虑t中有相同字符的情况,所以需要统计t中每个字符的出现次数
for (var i = 0; i < t.Length; i++)
{
AddItem(tDic, t[i]);
}
var left = 0;
var right = 0;
int areaL =0;
int ansL = s.Length+1;
while (right < s.Length)
{
if (right<s.Length&& tDic.ContainsKey(s[right]))
{
AddItem(sDic, s[right]);
}
while (CheckDic() && left <= right)
{
if (ansL> right-left+1)
{
ansL = right - left + 1;
areaL = left;
}
RemoveItem(sDic, s[left]);
left++;
}
right++;
}
if (ansL > s.Length) return "";
return s.Substring(areaL, ansL);
}
void AddItem(Dictionary<char, int> dic, char key)
{
if (dic.ContainsKey(key))
{
dic[key]++;
}
else
{
dic.Add(key, 1);
}
}
void RemoveItem(Dictionary<char, int> dic, char key)
{
if (dic.ContainsKey(key))
{
dic[key]--;
}
}
bool CheckDic()
{
foreach (var i in tDic)
{
if (sDic.ContainsKey(i.Key))
{
if (sDic[i.Key] < tDic[i.Key])
{
return false;
}
}
else
{
return false;
}
}
return true;
}
}
时间复杂度 : O(n)
其中n是数组的长度,只需要遍历一遍数组即可求得答案。
空间复杂度: O(1)
只需要常数级别的空间存放变量。
先考虑从左到右,找到t中第一个相同的字符,然后将字符存入_matchList及state,然后往下找。
当出现相同的时候存入state,再看_matchList中有没有,没有就加入,有就看是否==s[_maxLeft],否就跳过
是就找到最左侧不为空的state,并将_maxLeft=index。然后用类似的方式考虑从右到左。
最后看_matchList的长度是否与t一致,一样就提取s中_maxLeft到_maxRight的字符串。
BUG:忘记处理从右往左时,最右侧与最左侧相同的情况,于是换思路:看题解,看了滑动窗口的原理。
字典查找消耗很大,还是用hashmap会好一些