聚美优品的网站建设状况,福州帮人建网站公司,南充做网站,响应式网站 app76. 最小覆盖子串
问题#xff1a;
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串#xff0c;则返回空字符串 “” 。
注意#xff1a;
对于 t 中重复字符#xff0c;我们寻找的子字符串中该字符数量必…76. 最小覆盖子串
问题
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。
注意
对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串我们保证它是唯一的答案。
示例 1输入s ADOBECODEBANC, t ABC
输出BANC
解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。示例 2输入s a, t a
输出a
解释整个字符串 s 是最小覆盖子串。示例 3:输入: s a, t aa
输出:
解释: t 中两个字符 a 均应包含在 s 的子串中
因此没有符合条件的子字符串返回空字符串。提示m s.length
n t.length
1 m, n 105
s 和 t 由英文字母组成解决
核心思想在于窗口滑动并且在滑动的过程中通过维护一个字典代表各个元素还需要的个数
滑动窗口的思想 用i,j表示滑动窗口的左边界和右边界通过改变i,j来扩展和收缩滑动窗口可以想象成一个窗口在字符串上游走当这个窗口包含的元素满足条件即包含字符串T的所有元素记录下这个滑动窗口的长度j-i1这些长度中的最小值就是要求的结果。
步骤一 不断增加j使滑动窗口增大直到窗口包含了T的所有元素
步骤二 不断增加i使滑动窗口缩小因为是要求最小字串所以将不必要的元素排除在外使长度减小直到碰到一个必须包含的元素这个时候不能再扔了再扔就不满足条件了记录此时滑动窗口的长度并保存最小值
步骤三 让i再增加一个位置这个时候滑动窗口肯定不满足条件了那么继续从步骤一开始执行寻找新的满足条件的滑动窗口如此反复直到j超出了字符串S范围。
用一个字典need来表示当前滑动窗口中需要的各元素的数量一开始滑动窗口为空用T中各元素来初始化这个need当滑动窗口扩展或者收缩的时候去维护这个need字典例如当滑动窗口包含某个元素我们就让need中这个元素的数量减1代表所需元素减少了1个当滑动窗口移除某个元素就让need中这个元素的数量加1。 记住一点need始终记录着当前滑动窗口下我们还需要的元素数量我们在改变i,j时需同步维护need。 值得注意的是只要某个元素包含在滑动窗口中我们就会在need中存储这个元素的数量如果某个元素存储的是负数代表这个元素是多余的。比如当need等于{‘A’:-2,‘C’:1}时表示当前滑动窗口中我们有2个A是多余的同时还需要1个C。这么做的目的就是为了步骤二中排除不必要的元素数量为负的就是不必要的元素而数量为0表示刚刚好。 回到问题中来那么如何判断滑动窗口包含了T的所有元素结论就是当need中所有元素的数量都小于等于0时表示当前滑动窗口不再需要任何元素。 优化 如果每次判断滑动窗口是否包含了T的所有元素都去遍历need看是否所有元素数量都小于等于0这个会耗费O(k)O(k)O(k)的时间复杂度k代表字典长度最坏情况下k可能等于len(S)。 其实这个是可以避免的我们可以维护一个额外的变量needCnt来记录所需元素的总数量当我们碰到一个所需元素c不仅need[c]的数量减少1同时needCnt也要减少1这样我们通过needCnt就可以知道是否满足条件而无需遍历字典了。 前面也提到过need记录了遍历到的所有元素而只有need[c]0大于0时代表c就是所需元素
func minWindow(s string, t string) string {i:0 //滑动窗口先摁住左边界增加右边界有合适的窗口后再挪动左边界res:[]int{0,math.MaxInt32} dict : make(map[string]int) //key是string类型因为rune太痛苦了for _,j:range t{dict[string(j)]1 }needCnt : len(t) //needCnt可以帮我们快速检查目前还需要元素的总个数for j,c : range s{if dict[string(c)]0{//如果元素在字典中那就可以让value减一needCnt - 1 }dict[string(c)]-1if needCnt0{ //该窗口可以匹配成功for{ //将窗口左边界i向右移动旨在删除多余重复元素h:s[i]if dict[string(h)]0{break}dict[string(h)]1i1}if j-ires[1]-res[0]{ //维护res最终结果res[0],res[1]i,j}//既然已经该窗口计算完毕那我们就接着i1往后面继续寻找dict[string(s[i])]1 //后续i1会删掉当前左边界那我们就需要在字典里1needCnt1i1}}if res[1]len(s){return } else{return s[res[0]:res[1]1]}
}
