首页 > 极客资料 博客日记

76.最小覆盖子串 Golang实现

2024-09-23 20:30:03极客资料围观18

极客之家推荐76.最小覆盖子串 Golang实现这篇文章给大家,欢迎收藏极客之家享受知识的乐趣

题目描述:

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

题目分析:
看到这类最长最短子串等,则首选滑动窗口方法。按照滑动窗口的方法,重点应该是确定满足要求时窗口的状态: 这里是包含字符串t的所有元素就可以,不要求有序,那么使用哈希表来记录就是很好的办法,同时要求最短,即后续要优化,因为可能T的元素会在s中常重复出现,那么哈希表的值设置为频率就能很好达到——》元素出现,并且频率一次就是最短的状态。因为是字符,所以哈希表设计为 var targetFreq :=map[byte]int。 那么targetFreq的长度就代表了目标字符串的元素种类。

点击查看代码
func minWindow(s string, t string) string {
   if len(s)==0 || len(t)==0{return ""}

   left,right,matchCount:=0,0,0
   //记录最短序列的开始位置,结合最短长度即可得到最短序列
   start:=0
   //记录最短长度
   minLength := len(s)+1
   //记录目标序列的元素的种类和个数。这样无论元素是否有重复,只要这两个要求都满足就可以
   targetFreq := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        targetFreq[t[i]]++
    }

    //用于记录当前窗口中的元素种类数量情况
    windowFreq := make(map[byte]int)

    for right<len(s){
        charRight := s[right]
        right++
        //只统计目标序列中的元素即可。
        if _,exists:=targetFreq[charRight];exists{
            windowFreq[charRight]++
            //如果某个元素的数量已经满足了目标序列的数量要求,那么完成的元素数量++
            if windowFreq[charRight] == targetFreq[charRight] {
                matchCount++
            }
        }
        //所有元素数量已经符合要求,现在看能否缩小序列
        for matchCount == len(targetFreq){
            if right-left <minLength{
                minLength = right-left
                start = left
            }
             charLeft:= s[left]
             left++
            //    尝试缩小边界
             if _,exists:=targetFreq[charLeft];exists{
                 if windowFreq[charLeft] == targetFreq[charLeft]{
                     matchCount--
                 }
                 windowFreq[charLeft]--
             }
        }
    }
    if minLength == len(s)+1{return ""}
    return s[start:start+minLength]
}

版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!

标签:

相关文章

本站推荐

标签云