首页 > 代码库 > [leetcode]Minimum Window Substring @ Python
[leetcode]Minimum Window Substring @ Python
原题地址:https://oj.leetcode.com/problems/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.
解题思路:双指针思想,尾指针不断往后扫,当扫到有一个窗口包含了所有T的字符,然后再收缩头指针,直到不能再收缩为止。最后记录所有可能的情况中窗口最小的。
代码:
class Solution: # @return a string def minWindow(self, S, T): count1={}; count2={} for char in T: if char not in count1: count1[char]=1 else: count1[char]+=1 for char in T: if char not in count2: count2[char]=1 else: count2[char]+=1 count=len(T) start=0; minSize=100000; minStart=0 for end in range(len(S)): if S[end] in count2 and count2[S[end]]>0: count1[S[end]]-=1 if count1[S[end]]>=0: count-=1 if count==0: while True: if S[start] in count2 and count2[S[start]]>0: if count1[S[start]]<0: count1[S[start]]+=1 else: break start+=1 if minSize>end-start+1: minSize=end-start+1; minStart=start if minSize==100000: return ‘‘ else: return S[minStart:minStart+minSize]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。