[LC] 76. Minimum Window Substring
2021-01-30 10:16
标签：div get while elf input bec count The pre 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: Note: Time: O(N) [LC] 76. Minimum Window Substring 标签：div get while elf input bec count The pre 原文地址：https://www.cnblogs.com/xuanlu/p/11660721.htmlInput: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
"".class Solution:
def minWindow(self, s: str, t: str) -> str:
res = ‘‘
my_dict = {}
for char in t:
freq = my_dict.get(char, 0)
my_dict[char] = freq + 1
count, start, end, min_len = len(my_dict), 0, 0, sys.maxsize
res_end, res_start = 0, 0
while end != len(s):
char = s[end]
if char in my_dict:
my_dict[char] -= 1
if my_dict[char] == 0:
count -= 1
end += 1
while count == 0:
start_char = s[start]
if start_char in my_dict:
my_dict[start_char] += 1
if my_dict[start_char] > 0:
count += 1
if min_len > end - start:
min_len = end - start
res_end = end
res_start = start
start += 1
return s[res_start: res_end]
上一篇：apache启动错误 AH00072: make_sock: could not bind to address [::]:443 windows系统端口/进程查看
下一篇：数据结构与算法（线性表）
文章标题：[LC] 76. Minimum Window Substring
文章链接：http://soscw.com/index.php/essay/49087.html