这篇文章主要为大家展示了“leetcode如何实现最小覆盖子串”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“leetcode如何实现最小覆盖子串”这篇文章吧。
给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"说明：
-
如果 S 中不存这样的子串，则返回空字符串
""。 -
如果 S 中存在这样的子串，我们保证它是唯一的答案。
解题思路：
1，用hashmap存储s和t中字符出现的次数
2，移动右指针，对于s中的每个字符，如果出现在t中，且s中出现的次数不大于t中出现的次数，说明我们找到了一个匹配字符，记录下来fund
3，如果found和t的长度相同，说明找到了解
A，包含t中所有字符
B，包含了部分重复字符（没有记录到fund中），说明，有些字符在s中出现的频率大于t中出现的频率
4，如果左指针对应字符在s中频率大于t中的频率，则应该舍弃这个字符，即移动左指针，调整对应次数
5，如果次数和t中相等，说明我们找到了一个局部最优解，记录下来
6，右移左指针，并且减少fund，寻找下一个局部最优解。
func minWindow(s string, t string) string { src:=make(map[byte]int) dst:=make(map[byte]int) for i:=0;i<len(t);i++{ dst[t[i]]++ } start:=0 found:=0 min:=len(s) begin:=-1 for end:=0;end<len(s);end++{ src[s[end]]++ if src[s[end]]<=dst[s[end]]{ found++ } if found==len(t){ for start<end && src[s[start]]>dst[s[start]]{ src[s[start]]-- start++ } if end-start<min{ min=end-start begin=start } src[s[start]]-- start++ found-- } } if begin==-1{ return "" } return string(s[begin:begin+min+1])}
以上是“leetcode如何实现最小覆盖子串”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！
原创文章，作者：kirin，如若转载，请注明出处：https://blog.ytso.com/224034.html