LeetCode76.Minimum Window Substring
2021-04-06 21:24
标签：.com substring turn 基本 判断 tput XA 思路 窗口 题目： 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: 思路： 题目要求的时间复杂度为O(n)，意味着选定窗口大小，依次遍历字符串的暴力方法（时间复杂度为O(n^2)）不合适。 联想到“有序数组和中为S的两个数”问题的解法，可以尝试用指针移动的方式来遍历字符串，以达到O(n)的时间复杂度。 基本的思路是右指针从左向右遍历S，对每一个右指针问题，求可能的最短窗口（用左指针从左向右的遍历实现）。为了判断窗口的合法性，需要一个字典，存储目标字符串T中的元素在窗口中是否出现。 python的具体实现代码如下： 在leetcode上显示运行时间快过99%的提交方案 LeetCode76.Minimum Window Substring 标签：.com substring turn 基本 判断 tput XA 思路 窗口 原文地址：https://www.cnblogs.com/plank/p/9128237.htmlInput: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
"". 1 class Solution(object):
2 def minWindow(self, s, t):
3 if not s or not t:
4 return ""
5 need = {}
6 for char in t:
7 if char not in need:
8 need[char] = 1
9 else:
10 need[char] += 1
11 missing = len(t)
12 min_left = 0
13 min_len = len(s) + 1
14 left = 0
15 for right, char in enumerate(s):
16 if char in need:
17 need[char] -= 1
18 if need[char] >= 0:
19 missing -= 1
20 while missing == 0:
21 if right - left + 1 min_len:
22 min_left, min_len = left, (right - left + 1)
23 if s[left] in need:
24 need[s[left]] += 1
25 if need[s[left]] > 0:
26 missing += 1
27 left += 1
28 if min_len > len(s):
29 return ""
30 return s[min_left: min_left + min_len]
上一篇：宽带win10自启
文章标题：LeetCode76.Minimum Window Substring
文章链接：http://soscw.com/index.php/essay/72149.html