首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >76. Minimum Window Substring

76. Minimum Window Substring

作者头像
Dylan Liu
发布2019-07-01 13:15:26
4280
发布2019-07-01 13:15:26
举报
文章被收录于专栏:dylanliudylanliu

Description

tags: Hash Table, Two Pointers, String difficulty: Hard

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"  
Output: "BANC"  

Note:

If there is no such window in S that covers all characters in T, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Solution
  1. 创建一个包含所有T中字节的窗口
  2. 从左侧减小窗口大小,如果符合条件(包含所有T中字节),记录最小长度与起止位置
  3. 如果不符合条件,从右侧扩大窗口,使之符合条件
  4. 重复2、 3直到 S 最末端
func minWindow(s string, t string) string {
    if len(s) == 0 || len(t) == 0 {
        return ""
    }
    mapT := make([]int, 256)
    for i:=0;i<len(t);i++{
        mapT[int(t[i])]+=1
    }
    posPair := []int{-1,-1}
    counter := len(t)
    minWin := len(s)
    
    start :=0
    
    for index,val := range s{
        mapT[int(val)] -=1
        if mapT[int(val)] >= 0{
            counter--
        }
        
        for ;counter==0;start++ {
            if minWin > index - start {
                posPair[0] = start
                posPair[1] = index
                minWin = index - start
            }
            mapT[int(s[start])]+=1
            if mapT[int(s[start])] > 0 {
                counter++
            }
        }
    }
    if posPair[0] == -1 {
        return ""
    }
    return s[posPair[0]:posPair[1]+1]
}

这是一个滑动窗口的算法题,基本的滑动窗口算法窗口大小是固定的,本题是滑动窗口的一个变体应用。

基本滑动窗口

可以查看Window Sliding Technique

应用方向:求连续大小为K的子数组的最大最小的值,和,积,xor 等

例子:Given an array of integers of size ‘n’. Our aim is to calculate the maximum sum of ‘k’ consecutive elements in the array.

变体滑动窗口

基本滑动窗口大小是固定的,而一般滑动窗口的大小是需要我们自己计算的,本题就是一例,根据网友的总结10-line template that can solve most 'substring' problems, 很多的子字符串类题都可以使用这种方法。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Solution
  • 基本滑动窗口
  • 变体滑动窗口
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档