76. 最小覆盖子串

package main
import "fmt"
func minWindow(s string, t string) string {
    need :=make(map[byte]int)
    for i:=0;i<len(t);i++{
        need[t[i]]++
    }
    var left,right,match,minLen,resL,resR int
    window := make(map[byte]int)
    for right<=len(s)-1{
        if _,ok:=need[s[right]];ok{
            window[s[right]]++
            if window[s[right]]==need[s[right]] {
                match++
            }
        }
        for match ==len(need){//窗口匹配
            l := right-left+1
            if minLen==0||l<minLen {
                resL = left
                resR = right
                minLen = l
            }
            if v,ok:=need[s[left]];ok{
                window[s[left]]--
                if window[s[left]]<v{
                    match--
                }
            }
            left++
        }
        right++
    }
    if minLen==0 {
        return ""
    }
   return s[resL:resR+1]
}
func main() {
    fmt.Println(minWindow("ADOBECODEBANC","ABC"))
}

func minWindow(s string, t string) string {
    m := make(map[byte]int)
    tlen, slen := len(t), len(s)
    for i := 0; i < tlen; i++ {
        m[t[i]]++
    }
    hit, start, minlen, res := 0, 0, slen, ""
    for j := 0; j < slen; j++ {
        m[s[j]]--
        if  m[s[j]] >= 0 {
            hit++
        }
        for hit == tlen {
            if  minlen > j - start {
                minlen = j - start
                res = s[start:j+1]
            }
            m[s[start]]++
            if m[s[start]] > 0 {
                  hit--
            }
            start++
        }
    }
    return res
}
作者：binwang
链接：https://leetcode-cn.com/problems/minimum-window-substring/solution/go-by-binwang/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。