[leetcode]Minimum Window Substring @ Python
2024-10-19 03:52:09
原题地址: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]
最新文章
- 使用cmd打开java文件,报错:“错误,编码GBK的不可映射字符”
- article和section
- HTML5之FileReader的使用
- Gradle build设置自动log开关
- wpf 窗口程序下将datagrid导出为excel
- 每天一个linux命令(22):chgrp命令
- OS X open finder here in terminal
- javascript ES5 Object对象
- o2o家庭助手demo
- ios客户端base64上传图片到java服务器遇到的问题
- 六度分离--hdu1869
- 1.自己写一个计算器demo
- python派QQ邮件
- SVG基础以及使用Javascript DOM操作SVG
- CodeForces 300C Beautiful Numbers
- NoClassDefFoundError与ClassNotFoundException
- lua保留n位小数方法
- Python 库,资源
- PPT 遥控器
- 【BZOJ1025】[SCOI2009]游戏(动态规划)