一、题目
1、算法题目
“给定两个字符串st，返回字符串s中覆盖t所有字符的最小子串。”
题目链接：
来源：力扣（LeetCode）
链接：76. 最小覆盖子串 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
- 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1： 输入： s = "ADOBECODEBANC", t = "ABC" 输出： "BANC" 复制代码
示例 2： 输入： s = "a", t = "a" 输出： "a" 复制代码
二、解题
1、思路分析
哈哈 经典滑动窗口的题目。
题意要求返回字符串s中覆盖t全部字符的最小子串，可以将包含t的子串的看做可行窗口。
在滑动窗口中会有两个指针，一个用于延伸现有窗口的指针，一个用于收缩窗口的指针。
那如果判断当前串口包含所有t所需的字符呢？可以用一个哈希表来表示t中所有的字符及数量。
如果这个哈希表中的对应的个数都不小于t的哈希表中各个字符的个数，那么当前窗口是可行的。
2、代码实现
代码参考：
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; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
其中n是数组的长度，只需要遍历一遍数组即可求得答案。
空间复杂度： O(1)
只需要常数级别的空间存放变量。
三、总结
先考虑从左到右，找到t中第一个相同的字符，然后将字符存入_matchList及state，然后往下找。
当出现相同的时候存入state，再看_matchList中有没有,没有就加入，有就看是否==s[_maxLeft]，否就跳过
是就找到最左侧不为空的state，并将_maxLeft=index。然后用类似的方式考虑从右到左。
最后看_matchList的长度是否与t一致，一样就提取s中_maxLeft到_maxRight的字符串。
BUG：忘记处理从右往左时，最右侧与最左侧相同的情况，于是换思路：看题解，看了滑动窗口的原理。
字典查找消耗很大，还是用hashmap会好一些
