leetcode Minimum Window Substring

leetcode Minimum Window Substring

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).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

题目地址:leetcode Minimum Window Substring

题目大意: 给定两个字符串S和T,求在S中的一个窗格,使得T中所有字母都出现。

思路:

又是two pointers的思想。一个指针指向出现的所有字符的结尾,然后用一个开头指针看看能不能将窗格变短。

可以用数组target记录t中各个字符的个数。然后扫描s,并记录当前区间[start, i]的字符个数(用count数组)。当满足count中都大于target时,说明合法,此时尝试缩短区间(start++)

C++

 

另一种单数组版本写法:

但其实可以只用一个数组完成。

仍用target记录t中各个字符的个数,cnt = len(t)即需要的字符个数

然后扫描s,  若target[s[i]] > 0 ,则说明s[i]是t中的字符,cnt-=1

若cnt == 0,说明从[start, i]的都在t中,满足条件,此时尝试增大start,缩小区间。

C++

Python

 

 

本文是leetcode如下的题解

  • 76. Minimum Window Substring

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Minimum Window Substring
本文地址:https://www.hrwhisper.me/leetcode-minimum-window-substring/

您的支持将鼓励我继续创作!

Leetcode . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *