LeetCode0076.最小覆盖子串 Go语言AC笔记

时间复杂度：O(n)

解题思路

可以用滑动窗口解决的一道题。

哈希表tmap记录下字符串t每个字母的数目，哈希表smap记录窗口中每个字母的数目。

滑动窗口是覆盖子串的条件为，对于tmap中所有字母的数目smap的数目都要不小于它们。

在滑动窗口右指针移动到数组末端前，如果遇到字符串t中的字母就令smap对应字母的数目加1，接下来只要滑动窗口是覆盖子串，那就更新res且令smap中移出窗口的字母数目减1，left不断右移加1。

当right移动到字符串s最末端且滑动窗口不是覆盖子串时，res就是最后的最小覆盖子串。

AC代码

仿照官方题解写的，但也融入了自己的理解

func minWindow(s string, t string) string {
    smap,tmap:=make(map[byte]int,0),make(map[byte]int,0)
    for i:=0;i<len(t);i++{
        tmap[t[i]]++
    }
    check:=func()bool{
        //必须检查tmap而不是smap，因为smap的key个数可能少于tmap
        for k,v:=range tmap{
            if v>smap[k]{
                return false
            }
        }
        return true
    }
    res:=""
    for left,right:=0,0;right<len(s);right++{
        if tmap[s[right]]>0{
            smap[s[right]]++
        }
        for check()&&left<=right{
            if right-left+1<len(res)||res==""{
                res=s[left:right+1]
            }
            if tmap[s[left]]>0{
                smap[s[left]]--
            }
            left++
        }
    }
    return res
}

感悟

一开始想用一个tmap实现的，但debug了俩小时也没AC，后来还是仿照官方题解的双mapAC了。浪费了不少时间……