当前位置 博文首页 > Mr_dogyang的博客:Leetcode刷题记录 76. 最小覆盖子串
给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。
示例:
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明:
如果 S 中不存这样的子串,则返回空字符串 ""。
如果 S 中存在这样的子串,我们保证它是唯一的答案。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-window-substring
思路:采用双指针从左至右,
(1)右指针++,直到区间【left:right】存在T的所有字符;
(2)左指针++,直到区间【left:right】不再存在T的字符;
(3)重复以上两步,直到right到达S尾部。
注意:以下查找所有字符存在使用的哈希表,能够实现要求但是时间上没有通过Leetcode检测,不想进一步优化了就这样吧。
class Solution:
def minWindow(self, s: str, t: str) -> str:
left=0
right=0
lens=len(s)
MinNum=float("Inf")
Minno=float("Inf")
if(not s or len(t)>lens or not t):return ''
from collections import defaultdict
lookup = defaultdict(int)
for c in t:
lookup[c] += 1
while(right<lens):
if(not self.found(s[left:right+1],lookup)):
right+=1
else:
while(left<=right and self.found(s[left:right+1],lookup)):
if(MinNum>(right-left+1)):
MinNum= (right-left)+1
Minno=left
left+=1
right+=1
return s[Minno:Minno+MinNum] if Minno!=float("Inf") else ''
def found(self,subs:str,lookup:[])->bool:
from collections import defaultdict
looksubs = defaultdict(int)
for c in subs:
looksubs[c] += 1
for key in lookup:
try:
if(looksubs[key]<lookup[key]):
return False
except:
return False
return True
if __name__=="__main__":
print(Solution().minWindow("ADOBECODEBANC","ABC"))
?
cs